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
#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

const int max_n = 407;
const int INF = 1e9+7;
bool g[max_n][max_n];
int dist[max_n][max_n];
vector<pi> v1; vector<pi> v2;

queue<int> q;
void bfs(int ind, int n){
    q.push(ind); dist[ind][ind] = 0;
    //cout << "\nind: " << ind << '\n';
    while(!q.empty()){
        int v = q.front(); q.pop();
        //cout << "v: " << v << " dist: " << dist[ind][v] << '\n';
        rep(i,1,n){
            if(!g[v][i]) continue;
            if(dist[ind][i] != INF) continue;
            //cout << "add i\n";
            dist[ind][i] = dist[ind][v]+1;
            q.push(i);
        }
    }
}

bool comp(pi a, pi b){
    //true dla wiekszy dist
    if(dist[a.st][a.nd] == dist[b.st][b.nd]){
        if(a.st == b.st) return a.nd < b.nd;
        return a.st < b.st;
    }
    return dist[a.st][a.nd] > dist[b.st][b.nd];
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

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

        srand(34624357); //oby to byla szczesliwa liczba!

        int n; cin >> n;
        rep(i,1,n){
            string s; cin >> s;
            rep(j,1,n){
                if(s[j-1] == '1') g[i][j] = 1;
                else g[i][j] = 0;
                dist[i][j] = INF;
            }
        }

        rep(i,1,n) bfs(i,n);

        rep(i,1,n)
            rep(j,i+1,n){
                v1.pb({i,j});
                v2.pb({i,j});
            }
        random_shuffle(v1.begin(),v1.end()); 
        //sort(v1.begin(),v1.end(),comp); reverse(v1.begin(),v1.end());
        sort(v2.begin(),v2.end(),comp);

        /* cout << "dist:\n";
        rep(i,1,n){
            rep(j,1,n) cout << dist[i][j] << ' ';
            cout << '\n';
        } */

        //randomizowane???

        int ans = 0;
        rep(i,1,n) rep(j,1,n) ans = max(ans,dist[i][j]);

        for(auto x:v1){
            int a = x.st; int b = x.nd;
            int m = 0;
            for(auto y:v2){
                int i = y.st; int j = y.nd;
                int d = min(dist[i][j],dist[i][a]+dist[b][j]);
                d = min(d,dist[i][b]+dist[a][j]);
                m = max(m,d);
                if(m >= ans) break;
            }
            ans = min(ans,m);
            
        }
        cout << ans << '\n';

        v1.clear(); v2.clear();
    }

    return 0;
}

//g++ -O3 -static -Wall .cpp -std=c++17