Untitled

import java.util.Scanner;

public class Main {
    static int tc, n;
    static int[][] map = new int[12][12];
    static int[][] visited = new int[12][12];
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] chip = new int[2][12];
    static int minn = 987654, cnt = 0, dai = 0;

    static boolean checkMap(int x, int y) {
        return (x < n && y < n && x >= 0 && y >= 0);
    }

    static boolean checkHuong(int x, int y, int hgx, int hgy) {
        int tempx = x + hgx;
        int tempy = y + hgy;
        while (checkMap(tempx, tempy)) {
            if (visited[tempx][tempy] == 1) {
                return false;
            }
            tempx += hgx;
            tempy += hgy;
        }
        return true;
    }

    static void visit(int x, int y, int hgx, int hgy, int val) {
        int tempx = x + hgx;
        int tempy = y + hgy;
        dai = 0;
        while (checkMap(tempx, tempy) && map[tempx][tempy] == 0) {
            dai++;
            visited[tempx][tempy] += val;
            tempx += hgx;
            tempy += hgy;
        }
    }

    static void BT(int xx, int sum) {
        if (sum > minn) return;
        if (xx == cnt) {
            if (sum < minn) minn = sum;
            return;
        }
        int x = chip[0][xx];
        int y = chip[1][xx];
        if (x == -1 && y == -1) {
            BT(xx + 1, sum);
        } else {
            for (int i = 0; i < 4; i++) {
                if (checkHuong(x, y, dx[i], dy[i])) {
                    visit(x, y, dx[i], dy[i], 1);
                    BT(xx + 1, sum + dai);
                    visit(x, y, dx[i], dy[i], -1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        tc = scanner.nextInt();
        for (int t = 1; t <= tc; t++) {
            n = scanner.nextInt();
            minn = 987654;
            cnt = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    visited[i][j] = 0;
                    map[i][j] = scanner.nextInt();
                    if (map[i][j] == 1) {
                        if (i == 0 || i == n - 1 || j == 0 || j == n - 1) {
                            // Do nothing
                        } else {
                            chip[0][cnt] = i;
                            chip[1][cnt] = j;
                            cnt++;
                        }
                        visited[i][j] = 1;
                    }
                }
            }

            for (int i = 0; i < cnt; i++) {
                boolean[] ch = new boolean[4];
                for (int j = 0; j < 4; j++) {
                    ch[j] = checkHuong(chip[0][i], chip[1][i], dx[j], dy[j]);
                }
                if (!ch[0] && !ch[1] && !ch[2] && !ch[3]) {
                    chip[0][i] = -1;
                    chip[1][i] = -1;
                }
            }

            BT(0, 0);
            if (minn == 987654) {
                System.out.println("#" + t + " " + 0);
            } else {
                System.out.println("#" + t + " " + minn);
            }
        }
        scanner.close();
    }
}