#include <iostream>
#include <fstream>
#define MAX -1
using namespace std;
int n;
int arr[20][20];
int dR[4] = {-1, 0, 1, 0};
int dC[4] = {0, 1, 0, -1};
int dd[20][20];
int dem;
int Max;
void BackTrack(int i, int j) {
if (i == n - 1 && j == n - 1) {
Max = max(Max, dem);
return;
}
for (int k = 0; k < 4; k++) {
int x = i + dR[k];
int y = j + dC[k];
if (x >= 0 && x < n && y >= 0 && y < n && dd[x][y] == 0 && arr[x][y] != 1) {
dd[x][y] = 1;
if (arr[x][y] == 2)
dem += 1;
BackTrack(x, y);
if (arr[x][y] == 2)
dem -= 1;
dd[x][y] = 0;
}
}
}
int main() {
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 >> arr[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dd[i][j] = 0;
}
}
Max = MAX;
dem = 0;
dd[0][0] = 1;
BackTrack(0, 0);
cout << Max << endl;
}
}