题目描述

You've become addicted to the latest craze in collectible card games, PokeCraft: The Gathering. You've mastered the rules! You've crafted balanced, offensive, and defensive decks! You argue the merits of various cards on Internet forums! You compete in tournaments! And now, as they just announced their huge new set of cards coming in the year 2010, you've decided you'd like to collect every last one of them! Fortunately, the one remaining sane part of your brain is wondering: how much will this cost?

There are $C$ kinds of card in the coming set. The cards are going to be sold in "booster packs", each of which contains $N$ cards of different kinds. There are many possible combinations for a booster pack where no card is repeated. When you pay for one pack, you will get any of the possible combinations with equal probability. You buy packs one by one, until you own all the $C$ kinds. What is the expected (average) number of booster packs you will need to buy?

输入格式

The first line of input gives the number of cases, $T$. $T$ test cases follow, each consisting of a line containing $C$ and $N$.

输出格式

For each test case, output one line in the form

Case #$x$: $E$

where $x$ is the case number, starting from 1, and $E$ is the expected number of booster packs you will need to buy. Any answer with a relative or absolute error at most $10^{-5}$ will be accepted.

2
2 1
3 2

Case #1: 3.0000000
Case #2: 2.5000000

提示

Limits

• $1 \leq T \leq 100$

Small dataset(10 Pts)

• $1 \leq N \leq C \leq 10$

Large dataset(30 Pts)

• $1 \leq N \leq C \leq 40$