//Mateusz Kussowski
//PA 2025 day 1 A teleport

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <limits>
using namespace std;

int find_furthest(int n, vector<vector<int>> &D, int v){
    int furthest = 0, furthest_node = 0;
    for (int i = 0; i < n; i++){
        if(D[v][i] > furthest){
            furthest = D[v][i];
            furthest_node = i;
        }
    }
    return furthest_node;
}

int find_furthest_with_tp(int n, vector<vector<int>> &D, int v, int x, int y){ // teleport from x to y
    int furthest = 0, furthest_node = 0;
    for (int i = 0; i < n; i++){
        int eff = min({ D[i][x] + D[y][v], D[i][y] + D[x][v], D[i][v] });
        if(eff > furthest){
            furthest = eff;
            furthest_node = i;
        }
    }
    return furthest_node;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<string> graph(n);
        for (int i = 0; i < n; i++){
            cin >> graph[i];
        }

        const int INF = 1e9;
        vector<vector<int>> D(n, vector<int>(n, INF));
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if(i == j) {
                    D[i][j] = 0;
                }
                else if(graph[i][j] == '1'){
                    D[i][j] = 1;
                }
            }
        }
 
        for (int k = 0; k < n; k++){
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++){
                    if(D[i][k] + D[k][j] < D[i][j]){
                        D[i][j] = D[i][k] + D[k][j];
                    }
                }
            }
        }

        int origDiam = 0;
        int u, v;
        for(int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                origDiam = max(origDiam, D[i][j]);
                if(D[i][j] == origDiam){
                    u = i;
                    v = j;
                }
            }
        }

        //find a vertex that is the furthest from u and v
        int midvertex = 0, score = min({ D[u][0], D[v][0] });
        for(int i = 1; i < n; i++){
            int eff = min({ D[u][i], D[v][i] });
            if(eff > score){
                score = eff;
                midvertex = i;
            }
        }

        int u0 = midvertex;
        for(int i = 0; i < 3; ++i) u0 = find_furthest(n, D, u0);
        int v0 = find_furthest(n, D, u0);

        int u1 = find_furthest(n, D, 14 % n);
        for(int i = 0; i < 3; ++i) u1 = find_furthest(n, D, u1);
        int v1 = find_furthest(n, D, u1);

        int u2 = find_furthest(n, D, 27 % n);
        for(int i = 0; i < 3; ++i) u2 = find_furthest(n, D, u2);
        int v2 = find_furthest(n, D, u2);

        int u3 = find_furthest(n, D, 42 % n);
        for(int i = 0; i < 3; ++i) u3 = find_furthest(n, D, u3);
        int v3 = find_furthest(n, D, u3);

        int u4 = find_furthest(n, D, 55 % n);
        for(int i = 0; i < 3; ++i) u4 = find_furthest(n, D, u4);
        int v4 = find_furthest(n, D, u4);

        int u5 = find_furthest(n, D, 68 % n);
        for(int i = 0; i < 3; ++i) u5 = find_furthest(n, D, u5);
        int v5 = find_furthest(n, D, u5);

        int u6 = find_furthest(n, D, 71 % n);
        for(int i = 0; i < 3; ++i) u6 = find_furthest(n, D, u6);
        int v6 = find_furthest(n, D, u6);

        int u7 = find_furthest(n, D, 84 % n);
        for(int i = 0; i < 3; ++i) u7 = find_furthest(n, D, u7);
        int v7 = find_furthest(n, D, u7);

        int u8 = find_furthest(n, D, 97 % n);
        for(int i = 0; i < 3; ++i) u8 = find_furthest(n, D, u8);
        int v8 = find_furthest(n, D, u8);

        u = u0;
        v = v0;
        if(D[u1][v1] > D[u][v]){
            u = u1;
            v = v1;
        }
        if(D[u2][v2] > D[u][v]){
            u = u2;
            v = v2;
        }
        if(D[u3][v3] > D[u][v]){
            u = u3;
            v = v3;
        }
        if(D[u4][v4] > D[u][v]){
            u = u4;
            v = v4;
        }
        if(D[u5][v5] > D[u][v]){
            u = u5;
            v = v5;
        }
        if(D[u6][v6] > D[u][v]){
            u = u6;
            v = v6;
        }
        if(D[u7][v7] > D[u][v]){
            u = u7;
            v = v7;
        }
        if(D[u8][v8] > D[u][v]){
            u = u8;
            v = v8;
        }

        int candidate = 0;
        for (int a = 0; a < n; a++){
            for (int b = 0; b < n; b++){
                int eff = min({ D[a][b], D[a][u] + D[v][b], D[a][v] + D[u][b] });
                candidate = max(candidate, eff);
            }
        }

        int old_u = u, old_v = v;
 
        int best = candidate;
        for (int u = 0; u < n; u++){
            for (int v = u + 1; v < n; v++){
                int temp = find_furthest_with_tp(n, D, midvertex, u, v);
                for(int i = 0; i < 1; ++i) temp = find_furthest_with_tp(n, D, temp, u, v);
                int temp2 = find_furthest_with_tp(n, D, temp, u, v);

                int Btemp = find_furthest_with_tp(n, D, u, u, v);
                for(int i = 0; i < 1; ++i) Btemp = find_furthest_with_tp(n, D, Btemp, u, v);
                int Btemp2 = find_furthest_with_tp(n, D, Btemp, u, v);

                if(min({ D[temp][temp2], D[temp][u] + D[v][temp2], D[temp][v] + D[u][temp2] }) < min({ D[Btemp][Btemp2], D[Btemp][u] + D[v][Btemp2], D[Btemp][v] + D[u][Btemp2] })){
                    temp = Btemp;
                    temp2 = Btemp2;
                }
                

                int candidate = min({ D[temp][temp2], D[temp][u] + D[v][temp2], D[temp][v] + D[u][temp2] });
                bool earlyBreak = false;
                for (int a = 0; a < n && !earlyBreak; a++){
                    for (int b = a + 1; b < n; b++){
                        int eff = min({ D[a][b], D[a][u] + D[v][b], D[a][v] + D[u][b] });
                        candidate = max(candidate, eff);
                        if(candidate >= best){
                            earlyBreak = true;
                            break;
                        }
                    }
                }
                best = min(best, candidate);

                if(best <= (origDiam)/2){
                    break;
                }
            }
            if(best <= (origDiam)/2){
                break;
            }
        }
 
        cout << best << "\n";
    }
    return 0;
}