#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef vector <int> VI;
int c[24], cn = 0;

void facerot(VI a, VI &b, int i) {
	int d = i * 9;
	const static int p[] = {2, 5, 8, 1, 4, 7, 0, 3, 6};
	rep (j, 9) b[d + j] = a[d + p[j]];
}

void facecp(VI a, VI &b, int i, int j) {
	int d0 = i * 9, d1 = j * 9;
	rep (k, 9) b[d1 + k] = a[d0 + k];
}

void rot0(VI &a) {
	VI b(74);
	rep (i, 4) facecp(a, b, (i + 1) % 4, i);
	facerot(a, b, 4);
	facerot(a, b, 5);
	facerot(b, b, 5);
	facerot(b, b, 5);
	{
		int d = 54;
		const static int p[] = {1, 2, 3, 0, 5, 6, 7, 4};
		rep (i, 8) b[d + i] = a[d + p[i]];
	}
	{
		int d = 54 + 8;
		const static int p[] = {1, 2, 3, 0, 5, 6, 7, 4, 9, 10, 11, 8};
		rep (i, 12) b[d + i] = a[d + p[i]];
	}
	a = b;
}

void rot1(VI &a) {
	VI b(74);
	facecp(a, b, 0, 5);
	facecp(a, b, 4, 0);
	facecp(a, b, 2, 4);
	facecp(a, b, 5, 2);
	facerot(b, b, 4);
	facerot(b, b, 4);
	facerot(b, b, 2);
	facerot(b, b, 2);
	facerot(a, b, 3);
	facerot(a, b, 1);
	facerot(b, b, 1);
	facerot(b, b, 1);
	{
		int d = 54;
		const static int p[] = {4, 5, 1, 0, 7, 6, 2, 3};
		rep (i, 8) b[d + i] = a[d + p[i]];
	}
	{
		int d = 54 + 8;
		const static int p[] = {8, 10, 6, 4, 0, 9, 1, 5, 3, 11, 2, 7};
		rep (i, 12) b[d + i] = a[d + p[i]];
	}
	a = b;
}

void add(const VI &a) {
	c[cn] = 0;
	VI b(74), vis(74, 0);
	rep (i, 74) b[a[i]] = i;
	rep (i, 74) {
		if (vis[i]) continue;
		for (int j = b[i]; j != i; j = b[j]) vis[j] = 1;
		vis[i] = 1;
		c[cn]++;
	}
	cn++;
}

void calc(VI a) {
//	rep (i, 74) printf("%d ", a[i]);
//	puts("");
	add(a);
	rot0(a);
	add(a);
	rot0(a);
	add(a);
	rot0(a);
	add(a);
}

void out(VI a) {
	cout << "output vector" << endl;
	rep (i, a.size()) cout << a[i] << " ";
	cout << endl;
}

void init() {
	vector <int> a(74), b;
	rep (i, 74) a[i] = i;
	rep (i, 4) {
		b = a;
		rep (j, i) rot0(b);
//		if (!i) out(b);
		rot1(b);
//		if (!i) out(b);
		calc(b);
	}
	b = a;
	rot1(b);
	rot1(b);
	calc(b);

	b = a;
	calc(b);
}

const int Mod = 10007;

int pm(long long a, int b) {
	long long res = 1;
	while (b) {
		if (b & 1) res = res * a % Mod;
		a = a * a % Mod;
		b >>= 1;
	}
	return res;
}

int main() {
	init();
	int Tc, n;
	scanf("%d", &Tc);
	rep (ri, Tc) {
		printf("Case %d: ", ri + 1);
		scanf("%d", &n);
		long long ans = 0;
		rep (i, cn) {
			ans = (ans + pm(n, c[i])) % Mod;
		}
		ans = ans * pm(cn, Mod - 2) % Mod;
//		cout << "cn = " << cn << endl;
//		sort(c, c + cn);
//		rep (i, cn) cout << "c[" << i << "] = " << c[i] << endl;
		cout << ans << "\n";
	}
}