1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>

#define INF INT_MAX

using namespace std;

const int N = 403;
int adj[N][N];
int standard_dist[N][N];
int teleport_dist[N][N][N];    // max odleglosc, pierwszy arg to pierwszy koniec zerowej krawedzi, drugi arg to root peku, trzeci arg to odleglosc do drugiego konca krawedzi zerowej
pair<int,int> optimize[N][N];   // pierwszy, drugi arg odpowiadają tym w teleport_dist, para zawiera indeks od ktorego wystepuja stale last_freeze   
int counting[N];

void odleglosc(int *A, int *B, int n, int a, int x) {
    for(int i = 0; i <= n-1; i++) {
        counting[i] = -1;
    }

    for(int i = 1; i <= n; i++) {
        if(B[i] > counting[A[i]]) counting[A[i]] = B[i];
    }

    stack<pair<int,int>> s;
    for(int a = n-1; a >= 0; a--) {
        if(counting[a] != -1) {
            if(s.empty()) s.push({a, counting[a]});
            else {
                if(counting[a] > s.top().second) {
                    s.push({a, counting[a]});
                }
            }
        }
    }

    int d = 0;
    int last_freeze = 0;
    while(d <= n-1 && !s.empty()) {
        pair<int,int> p = s.top();
        s.pop();
        while(p.second + d <= p.first) {
            teleport_dist[a][x][d] = max(last_freeze, p.second + d);
            d++;
        }   
        last_freeze = p.first;
    }

    // while(d <= n-1) {
    //     teleport_dist[a][x][d] = last_freeze;
    //     d++;
    // }
    optimize[a][x] = {d, last_freeze};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                char c;
                cin >> c;
                if(c == '1') {
                    adj[i][j] = 1;
                }
                else {
                    adj[i][j] = 0;  
                }
            }
        }

        for(int v = 1; v <= n; v++) {
            queue<int> q;
            q.push(v);
            vector<int> dist(n + 1, -1);
            dist[v] = 0;

            while(!q.empty()) {
                int u = q.front();
                q.pop();

                for(int i = 1; i <= n; i++) {
                    if(adj[u][i] && dist[i] == -1) {
                        dist[i] = dist[u] + 1;
                        q.push(i);
                    }
                }
            }

            for(int i = 1; i <= n; i++) {
                standard_dist[v][i] = dist[i];
            }
        }

        for(int a = 1; a <= n; a++) {   // pierwszy wierzcholek krawedzi zerowej
            
            for(int x = 1; x <= n; x++) {   // wierzcholek którego pek rozwazamy
                // standard_dist[x][...] to lewy ciag
                // standard_dist[a][...] to prawy ciag
                odleglosc(standard_dist[x], standard_dist[a], n, a, x);
            }
        }
        
    
        int best = INF;
        for(int a = 1; a <= n; a++) {   // pierwszy wierzcholek krawedzi zerowej
            for(int b = a+1; b <= n; b++) {
                int local_best = 0;
                for(int x = 1; x <= n; x++) {
                    int teleport;
                    int standard_dist_a_x = standard_dist[a][x];
                    int standard_dist_b_x = standard_dist[b][x];
                    if(standard_dist_a_x > standard_dist_b_x) {
                        pair<int,int> p = optimize[a][x];
                        if(standard_dist_b_x < p.first) {
                            teleport = teleport_dist[a][x][standard_dist_b_x];
                        }
                        else {
                            teleport = p.second;
                        }
                    }
                    else {
                        pair<int,int> p = optimize[b][x];
                        if(standard_dist_a_x < p.first) {
                            teleport = teleport_dist[b][x][standard_dist_a_x];
                        }
                        else {
                            teleport = p.second;
                        }
                    }

                    local_best = max(local_best, teleport);
                }
                best = min(best, local_best);
            }
        }

        cout << best << "\n";
    }

    return 0;
}