#include<bits/stdc++.h>
using namespace std;
const int MAXN = 20005;
typedef long long LL;
LL f[MAXN],g[MAXN],h[MAXN];
const LL P = 152076289,G = 106,MOD = P;
const int N = 10000;
LL pm(LL a,LL n,LL m){
    LL r=1;
    for(;n;n>>=1,a=a*a%m)
        if(n&1)r=r*a%m;
    return r;
}
//和FFT类似,仅用于计算卷积,在FFT碰到精度问题或超时时可以考虑换用NTT
//注意传入的n必须为2的幂次,并且计算的结果都是mod P下的结果,
//如果数域范围不够大,可以用多个(P,g)分别计算,再用中国剩余定理还原结果
//如果题目中模的数比较不常见,如果模的数是素数p,且p-1有很多因子2,很可能
//就要用NTT, 几个可替换的(P,g)对:
//(2113929217,5),(1811939329,13),(2130706433,3)
void ntt(LL *a,size_t n,bool inv=false){
    // inv为true时表示逆运算;
    LL w=1,d=pm(G,(P-1)/n,P),t;
    size_t i,j,c,s;
    if(inv){
        for(i=1,j=n-1;i<j;swap(a[i++],a[j--]));
        for(t=pm(n,P-2,P),i=0;i<n;++i)a[i]=a[i]*t%P;
    }
    for(s=n>>1;s;s>>=w=1,d=d*d%P)
    for(c=0;c<s;++c,w=w*d%P)
    for(i=c;i<n;i+=s<<1){
        a[i|s]=(a[i]+P-(t=a[i|s]))*w%P;
        a[i]=(a[i]+t)%P;
    }
    for(i=1;i<n;++i){
        for(j=0,s=i,c=n>>1;c;c>>=1,s>>=1)j=j<<1|s&1;
        if(i<j)swap(a[i],a[j]);
    }
}
LL inv[MAXN],com[MAXN],cominv[MAXN]; 
void calcCom()
{
	inv[0] = 0;
	inv[1] = 1;
	for (int i = 2; i <=N; ++i)
		inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
	com[0] = cominv[0] = 1;
	for (int i = 1; i <=N; ++i){
		com[i] = com[i - 1] * i % MOD;
		cominv[i] = cominv[i - 1] * inv[i] % MOD;
	}
}
void solve(int l,int r)
{
	if (l==r)
	{
		//h[l] = (h[l] * pm(com[l-1],l-1,P)) % P;
		g[l] = (f[l] - h[l]) % P;
		if (g[l] < 0) g[l]+=P;
		return;
	}
	int mid = (l+r)/2;
	solve(l,mid);
	static LL a[MAXN],b[MAXN];
	int n = mid - l + 1,m = r-l;
	int s = 2;
	for (;s<n+m-1;s<<=1);
	for (int i=0;i<s;i++) b[i] = f[i+1] * cominv[i+1] % P;
	for (int i=0;i<s;i++) a[i] = l+i<=mid ? g[l+i] * cominv[l+i-1] % P : 0;
	ntt(a,s); ntt(b,s);
	for (int i=0;i<s;i++) a[i] = a[i] * b[i] % P;
	ntt(a,s,true);
	for (int i=mid+1;i<=r;i++) h[i] = (h[i] + a[i-l-1] * com[i-1] % P) % P;
	solve(mid+1,r);
}
int plist[10000], pcount = 0;

bool prime(int n) {
    int i;
    if ((n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || (n != 5 && !(n % 5)) || (n != 7 && !(n % 7))) {
        return false;
    }
    for (i = 0; plist[i] * plist[i] <= n; i++) {
        if (!(n % plist[i])) {
            return false;
        }
    }
    return n > 1;
}

void initPrime() {
    plist[pcount++] = 2;
    for (int i = 3; i < 50000; i += 2) {
        if (prime(i)) {
            plist[pcount++] = i;
        }
    }
}
vector<int> fact;
int main()
{
	freopen("1.in","r",stdin);
	int T,test = 0;
	scanf("%d",&T);
	calcCom();
	h[0] = g[0] = 0;
	/*
	initPrime();
	LL x = P - 1,j = 0;
	while (x > 1 && j < pcount)
	{
		if (x % plist[j] == 0) fact.push_back(plist[j]);
		while (x % plist[j] == 0) x/=plist[j];
		j++;
	}
	if (x > 1) fact.push_back(x);
	for (int i=2;i<P;i++)
	{
		bool flag = true;
		for (auto p:fact)
			if (pm(i,(P-1)/p,P) == 1) {
				flag = false;
				break;
			}
		if (flag){
			cout<<i<<endl;
			return 0;
		}
		
	} 
	/* 
	for (int i=2;i<=P;i++)
	{ 
		LL tmp = pm(i,P-1,P);
		if ((tmp % P) == 1) {
			cout<<"!!"<<i<<endl;
			//cout<<i<<endl;
			return 0;
		}
	}	
	*/
	while (T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		memset(h,0,sizeof(h));
		memset(g,0,sizeof(g));
		for (int i=1;i<=n;i++) f[i] = pm(m+1,i*(i-1)/2,P);
		solve(1,n);
		LL treeNum = pm(n,n-2,P) * pm(m,n-1,P) % P;
		LL ans = g[n] - treeNum < 0 ? (g[n]-treeNum)% P + P : (g[n] - treeNum) % P; 
		printf("Case #%d: %lld\n",++test,ans);
	}
}