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
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

// Funkcja BFS zwraca w wektorze dist odległości od start do wszystkich wierzchołków
void bfs_dist(int start, int n, const vector<vector<bool>> &adj, vector<int> &dist) {
    const int INF = 1e9;
    for(int i = 0; i < n; i++){
        dist[i] = INF;
    }
    dist[start] = 0;
    queue<int> q;
    q.push(start);

    while(!q.empty()){
        int u = q.front();
        q.pop();
        int dnow = dist[u];
        for(int v = 0; v < n; v++){
            if(adj[u][v] && dist[v] == INF){
                dist[v] = dnow + 1;
                q.push(v);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;  // liczba testów
    while(t--){
        int n;
        cin >> n;

        // Wczytujemy macierz sąsiedztwa
        vector<vector<bool>> adj(n, vector<bool>(n, false));
        for(int i = 0; i < n; i++){
            // Wczytujemy wiersz jako ciąg znaków '0'/'1'
            string row;
            cin >> row;
            for(int j = 0; j < n; j++){
                if(row[j] == '1'){
                    adj[i][j] = true;
                }
            }
        }

        // Obliczamy odległości: dist[u][v] = minimalna liczba krawędzi z u do v
        static vector<int> tmpDist(400);
        vector<vector<int>> dist(n, vector<int>(n));
        for(int u = 0; u < n; u++){
            bfs_dist(u, n, adj, tmpDist);
            for(int v = 0; v < n; v++){
                dist[u][v] = tmpDist[v];
            }
        }

        // Obliczamy bieżącą średnicę (max dist[u][v])
        int diameter = 0;
        for(int u = 0; u < n; u++){
            for(int v = 0; v < n; v++){
                diameter = max(diameter, dist[u][v]);
            }
        }

        // Jeśli średnica ≤ 1, teleport nie pomaga
        if(diameter <= 1){
            cout << diameter << "\n";
            continue;
        }

        // Tworzymy listę par (x,y), które są warte sprawdzenia
        // (np. w odległości >= diameter - 1). W praktyce można wężej wybierać
        vector<pair<int,int>> candidates;
        candidates.reserve(n*n);
        for(int x = 0; x < n; x++){
            for(int y = x+1; y < n; y++){
                if(dist[x][y] >= diameter - 1){
                    candidates.push_back({x, y});
                }
            }
        }

        int best = diameter;  // nie gorszy niż stara średnica
        // Sprawdzamy każdą parę (x,y) i wyliczamy "nową średnicę"
        for(auto &pr : candidates){
            int x = pr.first, y = pr.second;
            int new_diam = 0;
            // nowa_odl(a,b) = min(dist[a][b], dist[a][x] + dist[y][b], dist[a][y] + dist[x][b])
            for(int a = 0; a < n; a++){
                for(int b = a+1; b < n; b++){
                    int candDist = dist[a][b];
                    int c2 = dist[a][x] + dist[y][b];
                    if(c2 < candDist) candDist = c2;
                    int c3 = dist[a][y] + dist[x][b];
                    if(c3 < candDist) candDist = c3;

                    if(candDist > new_diam){
                        new_diam = candDist;
                        // Jeśli i tak przekroczyliśmy current best, można przerwać
                        if(new_diam >= best) break;
                    }
                }
                if(new_diam >= best) break;
            }
            if(new_diam < best){
                best = new_diam;
            }
        }

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

    return 0;
}