카드 수집

당신은 최신 유행 수집형 카드 게임인 PokeCraft: The Gathering에 중독되었다. 규칙을 완벽히 익혔다! 균형형, 공격형, 방어형 덱도 만들었다! 인터넷 포럼에서 여러 카드의 장점을 놓고 논쟁한다! 대회에도 참가한다! 그리고 이제, 그들이 2010년에 출시될 방대한 신규 카드 세트를 막 발표하자, 당신은 그 카드들을 마지막 하나까지 모두 수집하기로 했다! 다행히도 아직 제정신인 뇌의 한 부분이 이렇게 묻고 있다. 비용이 얼마나 들까?

출시될 세트에는 C종류의 카드가 있다. 카드는 "부스터 팩"으로 판매되며, 각 팩에는 서로 다른 종류의 카드 N장이 들어 있다. 카드가 중복되지 않는 부스터 팩의 가능한 조합은 많다. 팩 하나의 값을 지불하면 가능한 조합 각각을 같은 확률로 얻게 된다. C종류의 카드를 모두 소유할 때까지 팩을 하나씩 구매한다. 구매해야 하는 부스터 팩 수의 기댓값(평균)은 얼마인가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100

작은 데이터 세트

1 ≤ N ≤ C ≤ 10

큰 데이터 세트

1 ≤ N ≤ C ≤ 40

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 C와 N이 포함된 한 줄로 이루어진다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

Case #x: E

여기서 x는 1부터 시작하는 케이스 번호이고, E는 구매해야 하는 부스터 팩 수의 기댓값이다. 상대 오차 또는 절대 오차가 최대 10^{-5}인 답은 모두 정답으로 인정된다.