Untitled

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

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

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

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

	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) {
		visit[hang][cot]++;
		//sum += a[hang][cot];  cach 2
		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;
			}
		}

	}

	public static void unVisitRow(int hang, int cot) {
		visit[hang][cot]--;
		//sum -= a[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;
			}
		}
	}

	public static void backTrack(int hang, int numQueen, int sum) {
		if (numQueen == N) { // xet truoc dong 104
			ans = Math.max(ans, sum);
			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) {
				
				visitRow(hang, i);
				backTrack(hang + 1, numQueen + 1, sum+a[hang][i]);
				unVisitRow(hang, i);
			}
		}

	}

}