#include <bits/stdc++.h>

using namespace std;

const int mod=530600414;

long long a[202000],b[202000],c[202000],d[202000];

int main(){
	int T;
	scanf("%d",&T);

	a[3]=0;
	b[3]=1;
	c[3]=3;
	d[3]=1;
	
	a[4]=0;
	b[4]=3;
	c[4]=5;
	d[4]=1;
	
	for (int i=5;i<=201314;i++){
		d[i]=(d[i-2]+d[i-1])%mod;
		c[i]=(c[i-2]+c[i-1])%mod;
		a[i]=a[i-2]+a[i-1]+(d[i-1]*c[i-2]%mod)*d[i-2]%mod+b[i-1]*d[i-2]%mod-b[i-2]*d[i-1]%mod;
		a[i]=(a[i]+mod)%mod;
		
		b[i]=b[i-2]+b[i-1]+c[i-2]*d[i-1]%mod;
		b[i]%=mod;
		//printf("%3d %3lld %3lld %3lld %3lld\n",i,d[i],a[i],b[i],c[i]);
		//if (i>10) break;
	}

	for (int ti=1;ti<=T;ti++){
		int n;
		scanf("%d",&n);
		printf("Case #%d: %lld\n",ti,a[n]);
	}
	return 0;
}