#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1e9;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> dist(n, vector<int>(n, INF));
    
    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < n; j++) {
            if (row[j] == '1') {
                dist[i][j] = 1;
            }
        }
        dist[i][i] = 0;
    }

    // Floyd-Warshall Algorithm to compute all-pairs shortest paths
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    int maxDist = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            maxDist = max(maxDist, dist[i][j]);
        }
    }
    
    int minTankSize = maxDist;
    
    // Consider adding a teleport between every pair of cities (i, j)
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (dist[i][j] > 1) { // If there is no direct road
                vector<vector<int>> newDist = dist;
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < n; b++) {
                        newDist[a][b] = min(newDist[a][b], min(newDist[a][i] + newDist[j][b], newDist[a][j] + newDist[i][b]));
                    }
                }
                int newMaxDist = 0;
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < n; b++) {
                        newMaxDist = max(newMaxDist, newDist[a][b]);
                    }
                }
                minTankSize = min(minTankSize, newMaxDist);
            }
        }
    }
    
    cout << minTankSize << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}