Untitled

#include <iostream>
using namespace std;
int head = -1;
int tail = -1;
int queue[40009];
int queue1[40009];
void Enqueue(int queue[], int queue1[], int element,int element1, int& tail) {
    queue[tail] = element;
	queue1[tail] = element1;
	tail++;
}
void Dequeue(int queue[], int queue1[], int& head) {
    queue[head] = 0; 
	queue1[head] = 0;
    head++;
}
int Front(int queue[], int head) {
    return queue[head];
}

int main(){
	//freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int TestCase = 0;TestCase < T;TestCase++){
		int size;
		cin >> size;
		head = -1;
		tail = -1;
		int arr[201][201];
		int array[201][201];
		int x,y;
		int check = -1;
		for (int i = 0;i<size;i++){
			for(int j = 0;j<size;j++){
				cin >> arr[i][j];
				array[i][j] = arr[i][j];
				if(arr[i][j] == 2){
					arr[i][j] = 1;
					x = j;
					y = i;
				}
			}
		}
		Enqueue(queue,queue1,0,0,tail);
		arr[0][0] = 2;
		while(tail-head > 0){
			int cow = Front(queue, head);
			int row = Front(queue1, head);
			Dequeue(queue,queue1,head);
			if(row > 0){
				if(arr[row-1][cow] == 1) {
					Enqueue(queue,queue1,cow,row-1,tail);
					arr[row-1][cow] = arr[row][cow]+1;
				}
			}
			if(row < size-1){
				if(arr[row+1][cow] == 1) {
					Enqueue(queue,queue1,cow,row+1,tail);
					arr[row+1][cow] = arr[row][cow]+1;
				}
			}
			if(cow > 0){
				if(arr[row][cow-1] == 1) {
					Enqueue(queue,queue1,cow-1,row,tail);
					arr[row][cow-1] = arr[row][cow]+1;
				}
			}
			if(cow < size-1){
				if(arr[row][cow+1] == 1) {
					Enqueue(queue,queue1,cow+1,row,tail);
					arr[row][cow+1] = arr[row][cow]+1;
				}
			}
		}
		int count = arr[y][x];
		if(count != 1){
			head = -1;
			tail = -1;
			Enqueue(queue,queue1,x,y,tail);
			array[y][x] = 2;
			while(tail-head > 0){
				int cow = Front(queue, head);
				int row = Front(queue1, head);
				Dequeue(queue,queue1,head);
				if(row > 0){
					if(array[row-1][cow] == 1) {
						Enqueue(queue,queue1,cow,row-1,tail);
						array[row-1][cow] = array[row][cow]+1;
					}
				}
				if(row < size-1){
					if(array[row+1][cow] == 1) {
						Enqueue(queue,queue1,cow,row+1,tail);
						array[row+1][cow] = array[row][cow]+1;
					}
				}
				if(cow > 0){
					if(array[row][cow-1] == 1) {
						Enqueue(queue,queue1,cow-1,row,tail);
						array[row][cow-1] = array[row][cow]+1;
					}
				}
				if(cow < size-1){
					if(array[row][cow+1] == 1) {
						Enqueue(queue,queue1,cow+1,row,tail);
						array[row][cow+1] = array[row][cow]+1;
					}
				}
			}
			if(array[size-1][size-1] > 1){
				check = count + array[size-1][size-1]-4;
			}
		}
		
		cout << check << endl;
	}
	return 0;
}