#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
using namespace std;
typedef long long LL;
const int maxn=1001;
const LL MOD=105225319;
LL pm(LL a,LL n,LL p) {
	LL ret=1;
	for (a%=p;n;n>>=1,a=a*a%p)
		if (n&1) ret=ret*a%p;
	return ret;
}
LL mul(LL a,LL b) { return a*b%MOD; }

LL C[maxn][maxn];
LL h[maxn],g[maxn],f[maxn],F[maxn];
void cal2(LL N,LL M) {
	for (int i=1;i<=N;i++) h[i]=g[i]=f[i]=F[i]=0;

	h[1]=2; f[1]=2;
	for (int i=2;i<=N;i++) {
		for (int k=0;k<=i;k++) (h[i]+=C[i][k]*pm(M+1,k*(i-k),MOD))%=MOD;
		for (int k=1;k<i;k++) (g[i]+=mul(mul(C[i-1][k-1],f[k]),h[i-k]))%=MOD;
		f[i]=(h[i] + MOD-g[i])%MOD;
	}
	for (int i=1;i<=N;i++) f[i]=f[i]*pm(2,MOD-2,MOD)%MOD;
	F[0]=1;
	for (int i=1;i<=N;i++)
		for (int k=1;k<=i;k++) (F[i]+=mul(mul(C[i-1][k-1],f[k]),F[i-k]))%=MOD;
}

LL n,m;
int main() {
	for (int i=0;i<=1000;i++) {
		C[i][0]=1;
		for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
	}

	int T; scanf("%d",&T);
	for (int tt=1;T--;tt++) {
		scanf("%lld%lld",&n,&m);
		cal2(n,m);
		F[1]=0;
		printf("Case #%d: %lld\n",tt,F[n]);
	}
	return 0;
}