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

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

int pows2[34];

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

int doit(int N, int M)
{
        memset(field, 0, sizeof(int) * 70 * 70 * 110);
        /*for(int i = 0; i < M; ++i)
        {
                field[0][0][i] = 1;
        }*/
        
        field[0][0][0] = 1;

        for(int i = 1; i < N; ++i)
        {
                for(int j = 1; j < N; ++j)
                {
                        for(int k = 0; k < M; ++k)
                        {       
                                if(j <= i-1)
                                {
                                    field[i][j][k] += field[i-1][j][k];
                                }
                                field[i][j][k] += field[i-1][j-1][((M - 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]);
        return field[N-1][((N-1)/2) - 1][((M - pows2[N] % M) + M) % M];
}