Description:
Dragon loves lottery, he will try his luck every week. One day, the lottery company brings out a new form of lottery called accumulated lottery. In a normal lottery, you pick 7 numbers from N numbers. You will get reward according to how many numbers you match. If you match all 7 numbers, you will get the top prize for 1 billion dollars!!! Unlike normal lottery, an M-accumulated lottery allows you to pick M numbers from N numbers. If M is big enough, this may significantly increase your possibility to win. (Of course it cost more…)
Some people buy multiple accumulated lotteries to guarantee a higher possibility to get the top prize. Despite of this, it’s still not worthy to guarantee a top prize.Knowing this, Dragon changes his target to second tier prize.
To get a second tier prize, you need to contain all of the R numbers with M numbers picked.Given N, M and R, Dragon wants to know how many M-accumulated lotteries he needs to buy, so that he can guarantee that he can get at least the second tier prize.
Input:
The first line of input contains only one integer T, the number of test cases.
For each case, there’s a single line contains N, M and R(1<=R<=M<=N<=8).
Output:
Each output should occupy one line. Each line should start with "Case #i: ", with i implying the case number. For each case, just output the result with no other leading or tailing spaces.
Sample Input:
3
2 1 1
2 2 1
2 2 2
Sample Output:
Case #1: 2
Case #2: 1
Case #3: 1