Untitled

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

public class Princess {
	static int n;
	static int a[][];
	static int dx[] = { 0, 0, 1, -1 };
	static int dy[] = { 1, -1, 0, 0 };
	static int Qx[];
	static int Qy[];
	static int visit[][];
	static boolean timThayCongChua;
	static int indexPrincessX;
	static int indexPrincessY;

	static int d[][];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try {
			System.setIn(new FileInputStream("Princess"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int numTest = sc.nextInt();
		for (int tc = 1; tc <= numTest; tc++) {
			n = sc.nextInt();
			

			a = new int[n + 2][n + 2];
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					a[i][j] = sc.nextInt();
				}
			}
			timThayCongChua = false;
			Qx = new int[n * n];
			Qy = new int[n * n];
			visit = new int[n + 2][n + 2];
			d = new int[n + 2][n + 2];

			 BFS(1, 1, 2);
			//System.out.println("toi cong chua" + result1);
			if (timThayCongChua) {
				visit = new int[n + 2][n + 2];
				//d = new int[n + 2][n + 2];
				//d[indexPrincessX][indexPrincessY] = result1;
				//BFS(indexPrincessX, indexPrincessY);
				System.out.println(BFS(indexPrincessX, indexPrincessY));
//				System.out.println("indexPrincessX" + indexPrincessX);
//				System.out.println("indexPrincessY" + indexPrincessY);
			}
			else
				System.out.println("-1");
		}
	}

	public static int BFS(int x, int y, int gtriCongChua) {
		int front = 0;
		int rear = 0;

		Qx[rear] = x;
		Qy[rear] = y;
		rear++;
		visit[x][y] = 1;
		while (front != rear) {
			int tmpx = Qx[front];
			int tmpy = Qy[front];
			front++;

			for (int i = 0; i < 4; i++) {
				int xx = tmpx + dx[i];
				int yy = tmpy + dy[i];

				if (xx >= 1 && xx <= n && yy >= 1 && yy <= n
						&& visit[xx][yy] == 0) {

					if (a[xx][yy] == 1 ) {

						d[xx][yy] = d[tmpx][tmpy] + 1;
						visit[xx][yy] = 1;
						Qx[rear] = xx;
						Qy[rear] = yy;
						rear++;
					}

					if (a[xx][yy] == gtriCongChua) {
						timThayCongChua = true;
						indexPrincessX = xx;
						indexPrincessY = yy;
						d[xx][yy] = d[tmpx][tmpy] + 1;
						return d[xx][yy];
					}
				}
			}
		}
		return -1;

	}

	// bfs tu vi tri cong chua toi cuoi me cung
	public static int BFS(int xxx, int yyy) {
		int front = 0;
		int rear = 0;

		Qx[rear] = xxx;
		Qy[rear] = yyy;
		rear++;
		visit[xxx][yyy] = 1;
		while (front != rear) {
			int tmpx = Qx[front];
			int tmpy = Qy[front];
			front++;
			//System.out.println("tmpx = "+tmpx +"; tmpy ="+tmpy);
			if (tmpx == n && tmpy == n) {
				return d[tmpx][tmpy];
			}
			for (int i = 0; i < 4; i++) {
				int xx = tmpx + dx[i];
				int yy = tmpy + dy[i];

				if (xx >= 1 && xx <= n && yy >= 1 && yy <= n
						&& visit[xx][yy] == 0) {

					if (a[xx][yy] == 1) {
						//System.out.println("xx" + xx);
						//System.out.println("yy" + yy);
						

						d[xx][yy] = d[tmpx][tmpy] + 1;
						if (xx == n && yy == n) { // neu return o ngoai d[tempx][tempy] thi Queue van them luc xet lan can. tràn Q
							return d[xx][yy];
						}
						//System.out.println("buocdi" + d[xx][yy]);
						visit[xx][yy] = 1;
						Qx[rear] = xx;
						Qy[rear] = yy;
						rear++;
					}
				}
			}
		}
		
		return -1;

	}

}