Untitled

import java.io.FileInputStream;
import java.util.Scanner;

public class QuanHau {
	static int a[][];
	static int visit[][];
	static int N;
	static int ans;
	static int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
	

	static int debug = 1;

//	public static boolean checkAnToan(int hang, int cot) {
//		if (visit[hang][cot] != 0)
//			return false;
//		return true;
//	}

	public static boolean checkFullRow(int hang) {
		for (int i = 0; i < N; i++) {
			if (visit[hang][i] == 0)
				return true; // chua full
		}
		return false;
	}

	public static void visitRow(int hang, int cot) {
		if(debug==1)
			System.out.println("visit:");
		visit[hang][cot]++;
		for (int i = 0; i < 8; i++) {
			for (int t = 1;; t++) {
				int nextX = hang + dx[i] * t;
				int nextY = cot + dy[i] * t;
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
					visit[nextX][nextY]++;
				} else
					break;
			}
		}
		if (debug == 1) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					System.out.print(visit[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();
		}

		// for(int i=0; i<N; i++)
		// {
		// visit[hang][i]++;
		// if(i!=hang)
		// visit[i][cot]++;
		// }
		//
		// int xRow = hang+1;
		// int xCol = cot+1;
		// while(xRow<N&&xCol<N){
		// visit[xRow][xCol]++;
		// }
	}

	public static void unVisitRow(int hang, int cot) {
		if(debug==1)
			System.out.println("unvisit:");
		visit[hang][cot]--;
		for (int i = 0; i < 8; i++) {
			for (int t = 1;; t++) {
				int nextX = hang + dx[i] * t;
				int nextY = cot + dy[i] * t;
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N)
					visit[nextX][nextY]--;
				else
					break;
			}
		}
		if (debug == 1) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					System.out.print(visit[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();
		}
	}

	// public static void print() {
	// for (int i = 0; i < 4; i++) {
	// for (int j = 0; j < 4; j++) {
	// System.out.print(a[i][j] + " ");
	// }
	// System.out.println();
	// }
	// }

	public static void backTrack(int hang, int numQueen) {
		if (numQueen == N) {   //xet truoc dong 104
			ans++;
			return;
		}
		if (hang == N)
			return;

		if (!checkFullRow(hang))
			return;
		for (int i = 0; i < N; i++) { // tung vi tri trong hang
			if (visit[hang][i]==0) {
				if (debug == 1)
					System.out.println("row:" + hang + " cot" + i);
				
				visitRow(hang, i);
				backTrack(hang + 1, numQueen + 1);
				unVisitRow(hang, i);
			}
		}

	}

	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("QuanHau.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
			a = new int[N][N];
			ans = 0;
			visit = new int[N][N];
			backTrack(0, 0);
			System.out.println("Case #" + test_case + ": " + ans);
		}
	}

}