#12063Zeros and Ones

Binary numbers and their pattern of bits are always very interesting to computer programmers. In this problem you need to count the number of positive binary numbers that have the following properties:

• The numbers are exactly N bits wide and they have no leading zeros.
• The frequency of zeros and ones are equal.
• The numbers are multiples of K.

Input

The input file contains several test cases. The first line of the input gives you the number of test cases, T (1 ≤ T ≤ 100). Then T test cases will follow, each in one line. The input for each test case consists of two integers, N (1 ≤ N ≤ 64) and K (0 ≤ K ≤ 100).

Output

For each set of input print the test case number first. Then print the number of binary numbers that have the property that we mentioned. Illustration: Here’s a table showing the possible numbers for some of the sample test cases:

5
6 3
6 4
6 2
26 3
64 2

Case 1: 1
Case 2: 3
Case 3: 6
Case 4: 1662453
Case 5: 465428353255261088