#include<stdio.h>
#include<stdlib.h>
#include <string.h>

long long int field[70][70][110];
long long int doit(int, int);

int pows2[34];

int main(void)
{
        int testcases;
        int cnt = 1;
        int N, M;
        scanf("%d", &testcases);
        pows2[0] = 1;
        for(int i = 1; i < 32; ++i)
        {
                pows2[i] = pows2[i-1] * 2;
        }
        while(testcases--)
        {
                scanf("%d%d", &N, &M);
                printf("Case %d: ", cnt);
                cnt++;
                printf("%lld\n", doit(N, M));
        }
        return 0;
}

long long int doit(int N, int M)
{
        memset(field, 0, sizeof(long long int) * 70 * 70 * 110);        
        field[0][0][0] = 1;

        for(int i = 1; i < N; ++i)
        {
                for(int j = 0; j < N; ++j)
                {
                        for(int k = 0; k < M; ++k)
                        {       
                                if(j <= i-1)
                                {
                                    field[i][j][k] += field[i-1][j][k];
                                }
                                if(j >= 1)
                                {
                                    field[i][j][k] += field[i-1][j-1][((k - pows2[i-1] % M) + M) % M];                                     
                                }
                             //   printf("i=%d j=%d k=%d   %d\n", i, j, k, field[i][j][k]);
                         }
                }
        }
       // printf("pow %d\n", pows2[N]);
        //printf("looking up at %d %d %d\n", N-1, (N/2) - 1, (M - pows2[N] % M) % M); 
        return field[N-1][(N/2) - 1][((M - pows2[N-1] % M) + M) % M];
}