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

#ifdef DEBUG
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "(" << p.first << ", " << p.second <<")";
}
auto operator<<(auto &o, auto x)-> decltype(x.end(), o) {
    o << "{";int i = 0;
    for(auto e : x) o << ", "+!i++<<e;
    return o <<"}";
}
#define debug(x...) cerr << "["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif

#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define fi first
#define se second
typedef pair <int, int> pii;

constexpr int N = 407;
char con[N][N];
int dist[N][N];

int calc_for_edge(int a, int b, int bst, int n, const vector <pii> &sortd) {
    int res = 0;
    vector <int> dist_a(n);

    for (int i=0; i<n; ++i) {
        dist_a[i] = min(dist[a][i], dist[b][i]);
        if (i == a || i == b) {
            dist_a[i] = 0;
        }
        res = max(res, dist_a[i]);
        if (res >= bst) return bst;
    }

    for (const auto &[i, j] : sortd) {
        // taki byl dystans miedzy (i, j) 
        // teraz moze byc taki przechodzacy przez (a, b)
        // i -> a -> b -> j  lub i -> b -> a -> j
        int const neww = min(dist_a[i] + dist_a[j], dist[i][j]); 

        res = max(res, neww);
        if (res >= bst) return bst;
    }
    return res;
}


void test() {
    debug("TC______________________");
    int n; cin>>n;
    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            cin>>con[i][j];
            if (con[i][j] == '1') 
                dist[i][j] = dist[j][i] = 1;
            else if (i == j)
                dist[i][i] = 0;
            else
                dist[i][j] = dist[j][i] = 1001;
        }
    }
    
    for (int k=0; k<n; ++k) {
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    int res = 0;
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            res = max(res, dist[i][j]);
        }
    }
    
    vector <pii> sortd;
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            sortd.push_back({i, j});            
        }
    }

    sort(all(sortd), [&](pii &a, pii &b) {
        return dist[a.fi][a.se] > dist[b.fi][b.se];
    });

    vector<int> sh(n);
    iota(all(sh), 0);
    mt19937 g(12532565634912548ull);
    shuffle(all(sh), g);

    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            int ret = calc_for_edge(sh[i], sh[j], res, n, sortd);   
            res = min(ret, res);
        }
    }

    cout<<res<<'\n';
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t = 1; cin>>t;
  while (t--) {
    test();
  }
}