#include<iostream>
#include<cstdio>
#define N 64
#define M 4096
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int gcd(int x,int y)
{
	if (!y) return x;
	return gcd(y,x%y);
}
int T,n,mod,ans,inv[N+1],tong[N+1],length,pw[M+1],g[N+1][N+1];
unsigned __int128 dst;
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
int MDS(long long x)
{
	x-=((dst*x)>>62)*mod;
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void dfs(int x,int d,int res,bool op,int cnt,int rst)
{
	if (!x)
	{
		Adder(ans,1ll*pw[res+n-length+op]*rst%mod);
		return;
	}
	int dst;
	for (int i=min(x,d);i>=1;--i)
	{
		dst=res;
		for (int j=1;j<=length;++j) dst+=g[tong[j]][i];
		tong[++length]=i,dfs(x-i,i,dst+(i>>1),op|(i&1),(d==i?cnt:0)+1,MDS(1ll*MDS(1ll*rst*inv[i])*inv[(d==i?cnt:0)+1])),--length;
	}
	return;
}
int main()
{
	for (int i=1;i<=N;++i)
		for (int j=1;j<=N;++j)
			g[i][j]=gcd(i,j);
	T=read();
	for (int qt=1;qt<=T;++qt)
	{
		n=read(),mod=read(),dst=(1ull<<62)/mod,ans=0;
		if (n==1)
		{
			printf("Case #%d: 1\n",qt);
			continue;
		}
		inv[1]=pw[0]=1;
		for (int i=2;i<=n;++i) inv[i]=MD2(-1ll*inv[mod%i]*(mod/i)%mod);
		for (int i=1;i<=M;++i) pw[i]=2ll*pw[i-1]%mod;
		dfs(n,n,0,0,0,1);
		for (int i=1;i<=n;++i) ans=1ll*ans*inv[2]%mod;
		printf("Case #%d: %d\n",qt,ans);
	}
	return 0;
}