Untitled

package Queue;

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

public class Bai3 {
	static int n;
	static int[][] arr = new int[10][10];
	static boolean[][] visited = new boolean[10][10];
	static int maxres,res;
	static int[] rspin = { 0, 0, 1, -1 };
	static int[] cspin = { 1, -1, 0, 0 };

	public static void check(int i, int j) {
		if (arr[i][j] == 2) {
			res+=1;
		}
		visited[i][j] = true;
		if (i == n - 1 && j == n - 1) {
			maxres = maxres > res ? maxres : res;
		}
		for (int k = 0; k < 4; k++) {
			int new_r = i + rspin[k];
			int new_c = j + cspin[k];
			if (new_r >= 0 && new_r < n && new_c >= 0 && new_c < n
					&& arr[new_r][new_c] != 1 && visited[new_r][new_c] == false) {
				check(new_r, new_c);
			}
		}
		if (arr[i][j] == 2) {
			res -= 1;
		}
		visited[i][j] = false;
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Text"));

		Scanner scanner = new Scanner(System.in);
		int tc = scanner.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			n = scanner.nextInt();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					arr[i][j] = scanner.nextInt();
				}
			}
			maxres = res = 0;
			check(0, 0);
			System.out.println(maxres);

		}
	}
}