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
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("O0")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

#define pb push_back
#define F first
#define S second
#define ll long long
#define ld double long
#define ull unsigned long long
#define endl '\n'


const ll N = 3e5 + 36;
const ll M = 2e3 + 36;
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;
const ll MOD1 = 888888901;
const ll MOD2 = 999988901;
const ll X[8] = {1, -1, 2, 2, -2, -2, 1, -1};
const ll Y[8] = {2, 2, 1, -1, 1, -1, -2, -2};
const ld PI = 3.14159265358979323846;
const ld EPS = 1e-10;

//tree < pair < string, int >, null_type, less < pair < string, int > >, rb_tree_tag, tree_order_statistics_node_update > a;

//mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
mt19937 gen(19937);


signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL
    int t = 0;
    cin >> t;
    while (t--) {
       int n;
       cin >> n;
       vector<vector<int>> a(n, vector<int>(n, 0));
       for (int i(0); i < n; ++i) {
          string s;
          cin >> s;
          for (int j(0); j < n; ++j) {
             if (s[j] == '0'){
                a[i][j] = (i == j ? 0 : 5000);
             } else {
                a[i][j] = 1;
             }
          }
       }
       for (int k(0); k < n; ++k)
	      for (int i(0); i < n; ++i)
		      for (int j(0); j < n; ++j)
		         a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
		 
		 vector<pair<int,pair<int,int>>> b;
		 for (int i(0); i < n; ++i) {
		    for (int j(i + 1); j < n; ++j) {
		       b.pb({a[i][j], {i, j}});
		    }
		 }
		 sort(b.rbegin(), b.rend());
		 
		 int ans = b[0].F;
		 
		 for (int i(0); i < n; ++i){
		    for (int j(i + 1); j < n; ++j) {
		      int cnt = min({a[b[0].S.F][b[0].S.S], 
		                     a[b[0].S.F][i] + a[j][b[0].S.S],
		                     a[b[0].S.F][j] + a[i][b[0].S.S]});
		                     
		      if (cnt >= ans) continue;
		      
		      for (int l(1); l < int(b.size()); ++l) {
		         if (cnt >= b[l - 1].F) {
		            break;
		         }
		         
		         int now = min({a[b[l].S.F][b[l].S.S], 
		                       a[b[l].S.F][i] + a[j][b[l].S.S],
		                       a[b[l].S.F][j] + a[i][b[l].S.S]});
		                       
		         cnt = max(cnt, now);
		      }
		      ans = min(ans, cnt);
		    }
		 }
	
		 cout << ans << endl;
    }
    return 0;
}