"Wicked" is a popular game in country Moderdesh but the national Wicked team is losing consistently and comprehensively to other visiting foreign teams. So, MWB (Moderdesh Wicked Board) is facing a lot of trouble as local people do not turn out to see matches with international teams. So they are planning to adopt a new policy that will bring a lot of people to the stadium.
Wicked is a lengthy game that is played between robots built by two countries. So there are actually two teams of robots (it is said that all the human players got injured in an incident when angry mob attacked busses full of players in 2010 BC). The game can have as many as 108 rounds and in each round a team can score points within 1 to N (inclusive).
One of the teams plays first and scores T points in R rounds. Then the other team plays and try to score exactly T points in exactly R rounds. If the team playing second scores more than T points in R rounds then the game is a draw, if they score less than T points then the team playing first wins. If the team playing second scores exactly T points in R rounds, it wins the game. But MWB has changed the rules a bit to shorten the game. So first they allow a team to play exactly R rounds and suppose they score T points. But they don't allow the 2nd team to play the full R rounds (as in that case it is almost likely that the local team will lose), they rather give the 2nd team an intermediate state to start with. An intermediate state means that that they declare that the 2nd team has scored Tint points in Rint (1 ≤ Tint ≤ T, 1 ≤ Rint ≤ R) rounds, now they have to score exactly (T - Tint) points in exactly (R - Rint) rounds to win. This situation may be very easy or very difficult for the 2nd team so this gives the local team often some very good chance to win. But it is not possible to win from all intermediate states (as one can earn minimum 1 and maximum N points from each round). The states from which the 2nd team can manage a win are called winning states. Given the value of R, T and N your job is to find out the total number of winning states.
Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.
Each case starts with a line containing three integers R (10 ≤ R ≤ 108), T (10 ≤ T ≤ 4*108) and** N (2 ≤ N ≤ 20). The meaning of **R, T and N is given in the problem statement.
Output
For each case, print the case number and the total number of winning states.
Sample
| Sample Input | Sample Output |
|---|---|
2 10 20 5 10 20 3 | Case 1: 83 Case 2: 59 |