#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXN = 10, inf = 0x3f3f3f3f;
typedef std::pair<int,int>  pii;
using namespace std;

int n, ans;
int a[MAXN][MAXN];
vector<pii> ppl;
vector<pii> step;
vector<int> height;
priority_queue<int> waitQ, descendQ; // min
void input(){
    ppl.clear();
    step.clear();
    height.clear();
    cin >> n;
    rep(i, 0, n){
        rep(j, 0, n){
            int x; cin >> x;
            if(x == 1) ppl.pb({i, j});
            else if(x > 1) step.pb({i, j}), height.pb({x});
        }
    }
}
int simulate(int stp, vector<int> grp){
    int curT = 0;
    // init
    rep(i, 0, grp.size()){
        int dist = abs(ppl[grp[i]].first - step[stp].first) + abs(ppl[grp[i]].second - step[stp].second);
        waitQ.push({-(dist + 1)});
    }
    while(true){
        while(!descendQ.empty()){
            int endt = -descendQ.top();
            if(endt <= curT) descendQ.pop();
            else break;
        }
        while(!waitQ.empty()){
            int t = - waitQ.top();
            if((int) descendQ.size() < 3 && t <= curT){
                descendQ.push(-(curT + height[stp])); // 실수(22m) : t가 아니라 curT
                waitQ.pop();
            }else break;
        }
        if(waitQ.empty() && descendQ.empty()) break;
        curT++;
    }
    return curT;
}
void backtrack(int idx, vector<int> bipartate[2]){
    if(idx == ppl.size()){
        // simulate
        ans = min(ans, max(simulate(0, bipartate[0]), simulate(1, bipartate[1])));
        return;
    }
    bipartate[0].pb({idx});
    backtrack(idx+1, bipartate);
    bipartate[0].pop_back();
    bipartate[1].pb({idx});
    backtrack(idx+1, bipartate);
    bipartate[1].pop_back();
}
void process(){
    ans = inf;
    input();
    vector<int> bipartate[2];
    backtrack(0, bipartate);
    cout << ans << endl;
}
int main(){
    freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    rep(t, 1, tc+1){
        cout << "#" << t <<" ";
        process();
    }
    return 0;
}