In how many ways you can select K objects from N different circularly placed objects such that the selection does not contain any pair of distinct objects having distance less than D around the circle? Here distance is the minimum of clockwise and anticlockwise distance. Details in following figure:
Here, 5 objects {A, B, C, D, E} are placed circularly. Say, K = 2 and D = 2, then the 5 possible selections are {A, C}, {A, D}, {B, D}, {B, E}, {C, E}. A selection is considered to be different from the others if it contains at least 1 object which is not present in the other selection.
Input
First line of the input contains a positive integer T (T ≤ 5000). Each of the following T lines contains three positive integers N (1 ≤ N ≤ 1000), K (1 ≤ K ≤ N) and D (1 ≤ D ≤ 10), respectively.
Output
Foreachcase,printalineoftheform‘Case
2/2 Sample Output Case 1: 5 Case 2: 10 Case 3: 0 Case 4: 50