/*
먼저 풀리하는 것에 대해서 짜보도록 하겠습니다.
1 1 1 1 1 1 에서
2 2 2 2 2 2 으로 모든 숫자를 넣어줍니다.
중복 가능, 순열
*/
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define SIZE 11
int N, M, S;
struct pInfo {
int x, y, dis, num;
};
pInfo person[11];
struct sInfo {
int x, y;
};
sInfo stair[3];
int map[SIZE][SIZE];
int ans;
int personArr[11];
queue<int> s1_wait, s2_wait;
struct on_stair {
int num, sec;
};
queue<on_stair> s1, s2;
int s1_num, s2_num, s1_end, s2_end;
int sec;
int s1_time, s2_time;
int minVal = 2123456789;
int maxVal = 0;
void problemIn() {
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
if (map[i][j] == 1) {
M++; // 1명 부터 5명까지.
person[M].x = i;
person[M].y = j;
}
if (map[i][j] >= 2) {
S++;
stair[S].x = i;
stair[S].y = j;
}
}
}
}
void init() {
minVal = 2123456789;
maxVal = 0;
M = S = 0;
}
/*
1. 계단에서 모두 내려옴
2. 대기에서 계단 타기
3. 맵에서 계단 대기로로 이동
4. 모두 내려왔는지 확인하기.
*/
void update() {
s1_num = s2_num = s1_end = s2_end = 0;
//먼저 사람들과 선택된 계단과의 거리를 구하기.
for (int i = 1; i <= M; i++) {
if (personArr[i] == 1) {
person[i].dis = (abs(person[i].x - stair[1].x) + abs(person[i].y - stair[1].y));
person[i].num = 1;
s1_num++;
}
else if (personArr[i] == 2) {
person[i].dis = ((abs(person[i].x - stair[2].x) + abs(person[i].y - stair[2].y)));
person[i].num = 2;
s2_num++;
}
}
// 1번 계단에 대해서 시간 구하기.
sec = 0;
while (1) {
sec++;
//계단에서 모두 내려왔는지 확인
while (1) {
if (s1.empty())break;
if (s1.front().sec == sec) {
s1.pop();
s1_end++;
}
else {
break;
}
}
//대기에서 계단 타기
while (1) {
if (s1_wait.empty()) break; // 비어있으면 와일문 나가기.
if (s1.empty() || s1.size() < (map[stair[1].x][stair[1].y] < 3 ? map[stair[1].x][stair[1].y] : 3)) {
s1.push({ s1_wait.front(), sec + map[stair[1].x][stair[1].y] });
s1_wait.pop();
}
else {
break; // 계단의 인원이 3명으로 다 차있으면,
}
}
//map 에서 계단 대기로 이동
for (int i = 1; i <= M; i++) {
if (person[i].num == 1) {
if (person[i].dis == sec) {
s1_wait.push(i);
}
}
}
//모두 내려왔는지 확인하기.
if (s1_num == s1_end) {
s1_time = sec;
break;
}
}
// 2번 계단에 대해서 시간 구하기.
sec = 0;
while (1) {
sec++;
//계단에서 모두 내려왔는지 확인
while (1) {
if (s2.empty())break;
if (s2.front().sec == sec) {
s2.pop();
s2_end++;
}
else {
break;
}
}
//대기에서 계단 타기
while (1) {
if (s2_wait.empty()) break; // 비어있으면 와일문 나가기.
if (s2.empty() || s2.size() < (map[stair[2].x][stair[2].y] < 3 ? map[stair[2].x][stair[2].y] : 3)) {
s2.push({ s2_wait.front(), sec + map[stair[2].x][stair[2].y] });
s2_wait.pop();
}
else {
break; // 계단의 인원이 3명으로 다 차있으면,
}
}
//map 에서 계단 대기로 이동
for (int i = 1; i <= M; i++) {
if (person[i].num == 2) {
if (person[i].dis == sec) {
s2_wait.push(i);
}
}
}
//모두 내려왔는지 확인하기.
if (s2_num == s2_end) {
s2_time = sec;
break;
}
}
maxVal = max(s1_time, s2_time);
minVal = min(minVal, maxVal);
return;
}
void dfs(int depth) {
if (depth == (M+1)) {
update();
return;
}
for (int i = 1; i <= 2; i++) {
personArr[depth] = i;
dfs(depth + 1);
personArr[depth] = 0;
}
}
void solve() {
dfs(1);
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
problemIn();
solve();
cout << "#" << tc << " " << minVal << endl;
init();
}
return 0;
}