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
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using ll = long long;
using sz = size_t;
using namespace std;

// make the code less c++-readable:
template<class T> using v = vector<T>; 
template<class T> using vv = v<v<T>>; 
using vi = v<int>; using vll = v<ll>; using vvi = vv<int>; using vvll = vv<ll>;

// hai loading utilities
#define $T template<class T>
#define $Ts template<class... T>
$T T Load() { T v; cin >> v; return v; }
$T auto Loads(int n) { v<T> v; v.reserve(n); while(n--) v.emplace_back(Load<T>()); return v; }
$T auto Loads() { return Loads<T>(Load<int>()); }
template<class T, int N> auto Loada() { array<T, N> a; for (T& v: a) v = Load<T>(); return a; }
$Ts auto Cols(int rows) { tuple<v<T>...> t; while(rows--) [&]<sz... I>(index_sequence<I...>){(std::get<I>(t).push_back(Load<T>()), ...);}(index_sequence_for<T...>{}); return t; }
//$Ts auto Rows(int rows) { v<tuple<T...>> v; while(rows--) { v.emplace_back(Load<T>()...); } return v; } bugged :(
struct _aIV { $T operator vector<T>() { return Loads<T>(n); } sz n; };
struct _aI { $T operator T() { return Load<T>(); } _aIV operator()(sz n) { return {n}; } }; static inline _aI $;  /* int N = $;  vi Y = $(N); */
#define MAKE_LOADER(T, alias) \
  T alias() { return Load<T>(); }   /* int x = Int(); */\
  auto alias##s() { return Loads<T>(); }   /* vector<> xs = Ints(); */\
  auto alias##s(int n) { return Loads<T>(n); }   /* vector<> xs = Ints(7); */\
  template<int N> auto alias##a() { return Loada<T, N>(); }   /* array<> xs = Inta<7>();  */\
// line intentionally left blank
MAKE_LOADER(int, Int)
MAKE_LOADER(long long, LL)
MAKE_LOADER(char, Char)
MAKE_LOADER(string, String)
// kthxbye


void test() {
    
    const int N = $;
    
    vector<string> graf;
    for (int i = 0; i < N; ++i)
        graf.push_back(String());
    
    
    // F.-W., kopia z wiki:
    constexpr static int DUŻO = 87654321;
    vector<vector<int>> odl(N, vector<int>(N, DUŻO));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) odl[i][j] = 0;
            else if (graf[i][j] == '1') odl[i][j] = 1;
        }
    }
    
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                odl[i][j] = min(odl[i][j], odl[i][k] + odl[k][j]);
            }
        }
    }
    
    auto OdległośćPomiędzyGdybyTeleport = [&] (int skąd, int dokąd, int teleport1, int teleport2) {
        return min({
            odl[skąd][dokąd],
            odl[skąd][teleport1] + odl[teleport2][dokąd],
            odl[skąd][teleport2] + odl[teleport1][dokąd]
        });
    };
    
    map<int, vector<pair<int, int>>> mapa_odl;
    for (int i = 0; i < N; ++i)
        for (int j = i+1; j<N; ++j)
            mapa_odl[odl[i][j]].push_back({i, j});
            
    vector<pair<int, int>> pary_od_najdalszych;
    for (auto it = mapa_odl.crbegin(); it != mapa_odl.crend(); ++it) {      
        for (const auto [a, b] : it->second) {
            pary_od_najdalszych.push_back({a, b});
        }
    }
    
    
    int odpowiedź = DUŻO;    
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            // Mam pomysł: połączmy i-j teleportem!
            
            int maks_odl = 0;
            
            for (auto it = mapa_odl.crbegin(); it != mapa_odl.crend(); ++it) {                
                if (it->first <= maks_odl) break;
                for (const auto [a, b] : it->second) {
                    if (it->first <= maks_odl) break;
                    maks_odl = max(maks_odl, OdległośćPomiędzyGdybyTeleport(a, b, i, j));
                    if (maks_odl >= odpowiedź) break;
                }
                if (maks_odl >= odpowiedź) break;
            }
            
            odpowiedź = min(odpowiedź, maks_odl);
        }
    }
    
    cout << odpowiedź << endl;
    
    
    /*vector<vector<int>> postęp(N, vector<int>(N, 0)); // następna do sprawdzenia para odległych miast   
    using E = pair<int, pair<int, int>>;
    priority_queue<E, vector<E>, greater<E>> kolejka; // (aktualny maks, (teleport: i, j))
    for (int i = 0; i < N; ++i)
        for (int j = i+1; j < N; ++j)
            kolejka.push({0, {i, j}});
            
    while (true) {
        auto [maks, ij] = kolejka.top(); kolejka.pop();
        const auto [i, j] = ij;
        
        const int para = postęp[i][j];
        if (para >= pary_od_najdalszych.size()) {
            cout << maks << endl;
            return;
        }
        const auto [a, b] = pary_od_najdalszych[para];
        if (odl[a][b] <= maks) {
            cout << maks << endl;
            return;
        }
        
        maks = max(maks, OdległośćPomiędzyGdybyTeleport(a, b, i, j));
        
        ++postęp[i][j];
        kolejka.push({maks, ij});
    }*/
    
}

int main() {
    const int T = $;
    for (int t = 0; t < T; ++t) {
        test();
    }
    return 0;
}