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
#include <iostream>
#include <vector>
#include <list>
#include <tuple>

using namespace std;

const int inf = 1000000000;

int n;

typedef vector<list<int>> tways;

tuple<int, int> walk(int a, int b, const tways &ways) {
    vector<short> visited(n);
    for (int i = 0; i<n; ++i) {
        visited[i] = 0;
    }
    visited[a] = 1; visited[b] = 2;
    list<int> leavesA[2], leavesB[2];
    leavesA[0].push_front(a);
    leavesB[0].push_front(b);    
    int curr = 0; 
    int next = 1;
    int counter = 0;
    int lenA, lenB;
    lenA = lenB = 0;

    while (!leavesA[curr].empty() || !leavesB[curr].empty()) {
        bool incLen = false;
        while (!leavesA[curr].empty()) {
            int elA = leavesA[curr].front();
            leavesA[curr].pop_front();
            for (int i : ways[elA]) {
                if ( visited[i] == 0 || (visited[i] == 2 && visited[elA] != 3)) {
                    visited[i]++;
                    incLen = true;
                    if (visited[i] != 3) {
                        leavesA[next].push_back(i);
                    }
                } 
            }
        }
        if (incLen) lenA++;
        incLen = false;
        while (!leavesB[curr].empty()) {
            int elB = leavesB[curr].front();
            leavesB[curr].pop_front();
            for ( int i : ways[elB] ) {
                if ( visited[i] == 0 || (visited[i] == 1 && visited[elB] != 3)) {
                    visited[i] += 2;
                    incLen = true;
                    if (visited[i] != 3) {
                        leavesB[next].push_back(i);
                    }
                }
            }
        }
        if (incLen) lenB++; 

        counter++;
        curr = counter % 2;
        next = (counter + 1) % 2;
    }
    return {lenA, lenB};
}

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

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        tways ways(n);
        for ( int i = 0; i < n; ++i ) {
            for ( int j = 0; j < n; ++j ) {
                char c;
                cin >> c;
                if ( i != j && c == '1') {
                    ways[i].push_back(j);
                }
            }
        }
        int cand1 = -1, cand2 = -1;
        int lenA, lenB;
        int currDistance = inf;
        for ( int i = 0; i < n; i++ ) {
            for ( int j = i + 1; j < n; j++ ) {
                tie(lenA, lenB) = walk(i, j, ways);
                if (lenA + lenB < currDistance) {
                    currDistance = lenA + lenB;
                    cand1 = i; cand2 = j;
                }
            }
            
        }
        cout << currDistance << "\n";
    }
  
    return 0;
}