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
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fr(i,n) for(int i=0; i<(n); i++)
#define frx(i,a,b) for(int i=(a); i<=(b); i++)
#define ok(cond) cout << ((cond) ? "Yes" : "No") << "\n";
#define watch(x) cerr << (#x) << " == " << (x) << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef const int ci;
typedef const ll cll;
typedef const ld cld;
typedef pair<int,int> pii;
typedef set<int> si;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<int,ll>> vpill;


template<typename T1, typename T2>
istream& operator>>(istream& is, pair<T1,T2>& p) {
    return is >> p.st >> p.nd;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1,T2>& p) {
    return os << p.st << " " << p.nd;
}


template<typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    for (T x : v) {
        os << x << " ";
    }
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T>& s) {
    for (T x : s) {
        os << x << " ";
    }
    return os;
}

const int N = 400;
int g[N][N];
int dist[N][N];

int n;

void floyd_warshall() {
    fr(i, n){
        frx(j, i+1, n-1){
            if (g[i][j] == 0) {
                dist[i][j] = dist[j][i] = 2*N;
            } else {
                dist[i][j] = dist[j][i] = 1;
            }
        }
    }

    fr(k,n){
        fr(i,n){
            fr(j,n){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}


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

    int tests;
    cin>>tests;
    fr(C, tests){
        cin>>n;

        fr(i,n){
            fr(j,n){
                char c;
                cin>>c;
                g[i][j] = c-'0';
            }
        }

        floyd_warshall();
        
        int min_diam = 2*N;
        fr(i, n){
            frx(j, i+1, n-1){
                int diam = 0;        
                fr(s,n) {
                    frx(t, s+1, n-1) {
                        diam = max(diam, min({dist[s][t], 
                                              dist[s][i] + dist[j][t], 
                                              dist[s][j] + dist[i][t]}));
                    }
                    if (diam >= min_diam) {
                        break;
                    }
                }
                min_diam = min(min_diam, diam);
            }
        }
        cout << min_diam << "\n";
    }

    return 0;
}