Problem B

Next Generation Macaw

Macaw birds can give birth to a pair of new Macaw birds according to the following rule: Macaw birds are able to mate at the age of one year. Mating pair always produces one new pair (one male, one female) every year from the second year on.  A pair needs one complete year to produce one new pair after they have mated.

At the start, a newly born pair of Macaw birds (one male, one female) is put on a field. Let us assume that Macaw birds never die. At the very beginning of the second year, the original pair mates. There is one pair on the field during the first year. It takes one complete year for the pair to produce a new pair. Thus, there is still only one pair on the field during the second year.

At the very beginning of the 3rd year, the female produces a new pair. So now there are 2 pairs of Macaw birds on the field during the third year. At the very beginning of the fourth year, the original female produces a second pair, making 3 pairs in all on the field during the fourth year. At the end of the fourth year, the original female has produced yet another new pair, the female born two years ago produces her first pair also, making 5 pairs during the fifth year.

Now to be realistic, the Macaw birds have actually a fixed life time of (k + 0.5) years, where k is an integer. For example, if k = 3, then at the end of the third year, the number of pairs on the field are 2. At the very beginning of the fourth year, the original female produces a second pair.  However, the original pair also dies during the fourth year. Thus, the number of pairs on the field is 2 at the end of the fourth year. At the very beginning of the fifth year, the female born two years ago produces her first pair; making 3 pairs during the fifth year. Given n and k, you need to determine the total number of Macaw birds at the end of n-th year.

Input

First line of the input contains a positive integer T (T <= 100). Each of the following T lines contains two integers n (1 <= n <= 2*10⁹) and k (3 <= k <= 100), respectively.

Output

For each case, print a line of the form Case <x>: <y>, where x is the case number and y is the total number of Macaw birds at the end of n-th year. As the value of y can be quite large, print the value modulo 10007.

Sample Input	Output for Sample Input
3 1 3 2 3 3 3	Case 1: 2 Case 2: 2 Case 3: 4

Problemsetter: Anindya Das

Special Thanks: Hasnain Heickal, Md. Mahbubul Hasan