#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (int i=s;i<=t;i++)
#define pi acos(-1)
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef pair<PII, PII> PPP;
typedef pair<PII, int> PPI;
#define repp(i,s,t) for (int i=s;i>=t;i--)
template<class T> T sqr(T x) {return x*x;}
#define debug(x) cerr<<#x"="<<(x)<<endl;
#define pb(x) push_back(x);
const int maxn = 1200;
#define ori(x) x-'a'
const int mod = 105225319;
int n, m;
LL f[maxn], g[maxn], F[maxn];
LL fact[maxn], ifac[maxn];
LL calc(int a, int b)
{
	if (b == 0) return 1;
	if (b == 1) return a;
	LL xx = calc(a, b/2);
	xx = xx * xx % mod;
	if (b % 2) xx = xx * a % mod;
	return xx;
}
LL C(int n, int m)
{
	return fact[n] * ifac[m] % mod * ifac[n-m] % mod;
}
void inti()
{
	fact[0] = 1;
	ifac[0] = 1;
	rep(i,1,1000)
	{
		fact[i] = fact[i-1] * i % mod;
		ifac[i] = calc(fact[i], mod - 2);
	}
}
int main()
{
	int testdata;
	inti();
	scanf("%d",&testdata);
	rep(_t,1,testdata)
	{
		scanf("%d%d",&n,&m);
		m++;
		f[1] = 1;
		g[1] = 2;
		rep(i,2,n)
		{
			g[i] = 0;
			rep(j,0,i) g[i] = (g[i] + C(i,j) * calc(m, j * (i - j))) % mod;
			f[i] = g[i];
			rep(j,1,i-1)
				f[i] = (f[i] - C(i-1,j-1) * 2ll % mod * f[j] % mod * f[i - j]) % mod;
			f[i] = f[i] * calc(2, mod-2) % mod;
			f[i] = (f[i] + mod) % mod;
		}
		printf("Case #%d: %d\n", _t, n>1?f[n]:0);
	}	
}