Untitled

class Solution {
	static int[] visited;
	static int[] rings;
	static int[] prime;
	static int[] primeRing;
	static Scanner sc;
	static int sum = 0;

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

		for (int test_case = 1; test_case <= T; test_case++) {
			Answer = 0;

			int n = sc.nextInt();
			visited = new int[n];
			rings = new int[n];
			prime = new int[100];

			sum = 0;

			// input matrix
			for (int i = 0; i < n; i++) {
				rings[i] = sc.nextInt();
				visited[i] = 0;
			}

			caculatePrime();
			visited[0] = 1;
			backtrack(0, 0);

			System.out.println("Case #" + test_case + ": " + sum);
			visited = null;
			rings = null;
		}
	}

	private static void caculatePrime() {
		for (int i = 0; i < rings.length; i++) {
			for (int j = i + 1; j < rings.length; j++) {
				int sum = rings[i] + rings[j];
				if (isPrime(sum)) {
					prime[sum] = 1;
				}
			}
		}
	}

	static boolean isPrime(int sum) {
		for (int i = 2; i <= Math.sqrt(sum); i++) {
			if (sum % i == 0) {
				return false;
			}
		}
		return true;
	}

	private static void backtrack(int node, int prev) {// i la dinh dang xet
		if (node == rings.length - 1) {
			if (prime[rings[prev] + rings[0]] == 1) {
				sum++;
			}
			return;
		}
		for (int i = 1; i < rings.length; i++) {
			if (visited[i] == 0) {
				if (prime[rings[prev] + rings[i]] == 1) {
					visited[i] = 1;
					backtrack(node + 1, i);
					visited[i] = 0;
				}
			}
		}
	}

	private static boolean isOK(int i) {
		for (int j = 0; j < rings.length; j++) {
			if (visited[j] == 0) {
				int sumRings = rings[i] + rings[j];
				if (sumRings % 2 != 0) {
					return true;
				}
			}
		}
		return false;
	}
}