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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)

#define INF 1000000000

class Graph {
    int n;
    vector<string> graph;
    vector<vector<int>> d;

public:
    explicit Graph(int n) : n(n) {
        graph.resize(n);
        d.assign(n, vector(n, INF));
    }

    void readData() {
        REP(i, n) {
            cin >> graph[i];
        }
    }

    void calcDist() {
        REP(i, n) {
            REP(j, n) {
                if(i == j)
                    d[i][j] = 0;
                else if(graph[i][j] == '1')
                    d[i][j] = 1;
            }
        }

        REP(k, n) {
            REP(i, n) {
                REP(j, n) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

    int origDist() {
        int origD = 0;
        REP(i, n) {
            REP(j, n) {
                origD = max(origD, d[i][j]);
            }
        }
        return origD;
    }

    int run() {
        int origDiam = origDist();
        int low = 0, high = origDiam, ans = origDiam;
        while(low <= high){
            int mid = (low + high) / 2;
            bool possible = false;
            for (int u = 0; u < n && !possible; u++){
                for (int v = u + 1; v < n && !possible; v++){
                    bool valid = true;
                    for (int i = 0; i < n && valid; i++){
                        for (int j = i + 1; j < n && valid; j++){
                            int newd = min({d[i][j], d[i][u] + d[v][j], d[i][v] + d[u][j]});
                            if(newd > mid){
                                valid = false;
                            }
                        }
                    }
                    if(valid) {
                        possible = true;
                    }
                }
            }
            if(possible){
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
};

int main() {
    int t;
    cin >> t;
    REP(tc, t) {
        int n;
        cin >> n;
        Graph g(n);
        g.readData();
        g.calcDist();
        cout << g.run() << endl;
    }
    return 0;
}