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 ( 1T100). Then T test cases will follow, each in one line. The input for each test case consists of two integers, N ( 1N64) and K ( 0K100).

Output 

Sample Input 

5
6 3
6 4
6 2
26 3
64 2

Sample Output 

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

Illustration: Here's a table showing the possible numbers for some of the sample test cases:

動態方程, DP[zeros][ones][mod]
DP[i+1][j][(l<<1)%k] += DP[i][j][l];
DP[i][j+1][((l<<1)+1)%k] += DP[i][j][l];

#include <stdio.h>
#include <string.h>
long long DP[34][34][100];
int main() {
    int t, n, k;
    int i, j, l, Case = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &k);
        printf("Case %d: ", ++Case);
        if(n&1 || k == 0) {
            puts("0");
            continue;
        }
        memset(DP, 0, sizeof(DP));
        /*[zeros][ones][mod];*/
        DP[0][1][1%k] = 1;
        n /= 2;
        for(i = 0; i <= n; i++) {
            for(j = 0; j <= n; j++) {
                for(l = 0; l < k; l++) {
                    DP[i+1][j][(l<<1)%k] += DP[i][j][l];
                    DP[i][j+1][((l<<1)+1)%k] += DP[i][j][l];
                }
            }
        }
        printf("%lld\n", DP[n][n][0]);
    }
    return 0;
}