PRINCESS
#include <iostream>
#define MAX_SIZE 1000
using namespace std;
// Implement Queue
class Queue {
private:
int a[MAX_SIZE];
int front;
int rear;
public:
Queue() {
front = -1;
rear = -1;
}
bool isFull() {
return front == 0 && rear == MAX_SIZE - 1;
}
bool isEmpty() {
return front == -1;
}
void enQueue(int x) {
if (isFull()) {
cout << "Queue is full" << endl;
}
else {
if (front == -1) front = 0;
a[++rear] = x;
}
}
int deQueue() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
else {
int x = a[front];
if (front >= rear) {
front = -1;
rear = -1;
}
else {
front++;
}
return x;
}
}
void display() {
for (int i = front; i <= rear; i++) {
cout << a[i] << endl;
}
}
};
// Princess
int N;
int dx[] = {1,-1, 0, 0};
int dy[] = {0, 0, 1,-1};
int p[200][200] = { 0 };
int visited[200][200] = { 0 };
int cnt[200][200] = { 0 };
int BFS(int x, int y) {
bool isFind = false;
Queue qx, qy;
qx.enQueue(x);
qy.enQueue(y);
visited[x][y] = 1;
// cout << x << " " << y << endl;
while (!qx.isEmpty() && !qy.isEmpty()) {
int topx = qx.deQueue();
int topy = qy.deQueue();
for (int k = 0; k < 4; k++){
int x1 = topx + dx[k];
int y1 = topy + dy[k];
if (x1 >= 0 && x1 < N && y1 >= 0 && y1 < N && p[x1][y1] != 0 && visited[x1][y1] != 1) {
// cout << x1 << " " << y1 << endl;
cnt[x1][y1] = cnt[topx][topy] + 1;
visited[x1][y1] = 1;
if (p[x1][y1] == 2) isFind = true;
if (x1 == N - 1 && y1 == N - 1 && isFind == true) {
return cnt[4][4];
}
qx.enQueue(x1);
qy.enQueue(y1);
}
}
}
return -1;
}
void reset() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cnt[i][j] = 0;
visited[i][j] = 0;
}
}
}
int main() {
freopen("input.txt", "r", stdin);
int T; cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> p[i][j];
}
}
reset();
cout << BFS(0, 0) << endl;
}
return 0;
}