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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h>
using namespace std;

const int n_max = 502;
vector<string> graph;
int odl[n_max][n_max];
vector<pair<int, int>> odl_sorted_one[n_max];

void init_odl(int k, int n){
    for(int i = 0; i <= n; i++){
        odl[k][i] = -1;
    }
    queue<pair<int, int>> next;
    next.push({k, 0});
    while(!next.empty()){
        auto [v, w] = next.front();
        next.pop();
        if(odl[k][v] != -1){
            continue;
        }
        odl[k][v] = w;
        for(int i = 0; i < n; i++){
            if(graph[v-1][i] == '1'){
                next.push({i+1, w + 1});
            }
        }
    }
    odl_sorted_one[k].clear();
    for(int i = 1; i <= n; i++){
        odl_sorted_one[k].push_back({odl[k][i], i});
    } 
    sort(odl_sorted_one[k].begin(), odl_sorted_one[k].end());
    //reverse(odl_sorted_one[k].begin(), odl_sorted_one[k].end());   
}

int solve_teleports(int a, int b, int last_ans, int n){
    vector<pair<int, int>> odl_sorted;
    vector<int> done(n+3);
    
    int ptr_a = 0, ptr_b = 0;
    while(ptr_a < n and ptr_b < n){
        if(done[odl_sorted_one[a][ptr_a].second] == 1){
            ptr_a++;
            continue;
        }
        if(done[odl_sorted_one[b][ptr_b].second] == 1){
            ptr_b++;
            continue;
        }
        if(odl_sorted_one[b][ptr_b].first >= odl_sorted_one[a][ptr_a].first){
            odl_sorted.push_back({odl_sorted_one[a][ptr_a]});
            done[odl_sorted_one[a][ptr_a].second] = 1;
            ptr_a++;
        }else{
            odl_sorted.push_back({odl_sorted_one[b][ptr_b]});
            done[odl_sorted_one[b][ptr_b].second] = 1;
            ptr_b++;    
        }
    }
    reverse(odl_sorted.begin(), odl_sorted.end());
    done.clear();

    // for(int i = 1; i <= n; i++){
    //     if(i == a or i == b){
    //         continue;
    //     }
    //     odl_sorted.push_back({min(odl[a][i], odl[b][i]), i});
    // }
    //return 0;

    // sort(odl_sorted.begin(), odl_sorted.end());
    // reverse(odl_sorted.begin(), odl_sorted.end());
    int ans_tmp = odl_sorted[0].first;
    for(int i = 0; i < odl_sorted.size(); i++){
        auto [wv, v] = odl_sorted[i];
        if(wv * 2 <= ans_tmp){
            break;
        }
        for(int j = i + 1; j < odl_sorted.size(); j++){
            auto [wu, u] = odl_sorted[j];
            if(wv + wu <= ans_tmp){
                break;
            }
            ans_tmp = max(ans_tmp, min(wv + wu, odl[u][v]));
        }
        if(ans_tmp >= last_ans){
            return last_ans;
        }
    }

    return min(ans_tmp, last_ans);
}

void solve(){
    int n;
    cin >> n;
    graph.clear();
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        graph.push_back(s);
    }
    for(int i = 1; i <= n; i++){
        init_odl(i, n);
    }
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j<= n; j++){
    //         cout << odl[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // for(int i = 1; i <= n; i++){
    //     for(int j = 0; j< n; j++){
    //         cout << odl_sorted_one[i][j].first << ' ';
    //     }
    //     cout << '\n';
    // }
    int ans = 1e9;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            ans = solve_teleports(i, j, ans, n);
        }
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}