#include <iostream>
using namespace std;
const int MAX_SIZE = 201;
const int INF = 1e9;
int in[MAX_SIZE][MAX_SIZE];
int dem[MAX_SIZE][MAX_SIZE];
int Qx[MAX_SIZE * MAX_SIZE];
int Qy[MAX_SIZE * MAX_SIZE];
int Qd[MAX_SIZE * MAX_SIZE];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
void push(int x, int y, int d, int &r) {
r++;
Qx[r] = x;
Qy[r] = y;
Qd[r] = d;
}
void pop(int &x, int &y, int &d, int &f) {
f++;
x = Qx[f];
y = Qy[f];
d = Qd[f];
}
int BFS(int startX, int startY, int endX, int endY, int n) {
int r = -1, f = -1;
push(startX, startY, 0, r);
while (r != f) {
int x, y, d;
pop(x, y, d, f);
if (x == endX && y == endY) {
return dem[x][y];
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && in[nx][ny] != 0 && dem[nx][ny] == INF) {
push(nx, ny, d + 1, r);
dem[nx][ny] = d + 1;
}
}
}
return -1;
}
int main() {
freopen("input.txt","r",stdin);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int startX, startY;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> in[i][j];
dem[i][j] = INF;
if (in[i][j] == 2) {
startX = i;
startY = j;
}
}
}
int d1 = BFS(1, 1, startX, startY, n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dem[i][j] = INF;
}
}
int d2 = BFS(startX, startY, n, n, n);
if (d1 == -1 || d2 == -1) {
cout << -1 << endl;
} else {
cout << d1 + d2 << endl;
}
}
return 0;
}