Climbing Stairs

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

There is a stair, the length of which is n. The person is at No.0 step at first, and his destination is the step NO.n. He has two kind of way forward: 1. One step forward(x->x+1). 2. Two steps forward(x->x+2). But there is an evil trap in one step, and the person has to skip it. That means if the number of that step is k, the person has to a two steps forward at the step k-1. In addition, due to a two steps forward very arduous. So he can\'t often use it. To simplify the problem, in the process of climbing stairs, the person had used the number of times one step forward must be not less than the number of times two steps forward. Now the person wants to know, how many methods exist that he can finish the climbing?

Input

Input includes T (T <= 100) cases, the first line contains the number of cases, then T line follows ,each group of data contains two integers n (3 < = n < = 100) the length of the Stairs, k (1 < k < = n-1)the position of the evil trap(that means you must make two steps forward at k - 1).
 

Output

Output the total number of methods like the sample output, to prevent the method is excessive, the answer is MOD 10007.Output the total number of methods like the sample output, to prevent the method is excessive, the answer is MOD 10007.

Sample Input

3
3 2
4 3
6 3

Sample Output

Case 1: 1
Case 2: 1
Case 3: 2

Hint

Source

2012年"浪潮杯"山东省第三届ACM大学生程序设计竞赛(热身赛)