#include <iostream>

using namespace std;

const int NMAX = 407;
const int INF = 1e9+7;

int dp[NMAX][NMAX];

void floydWarshall(int n){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dp[i][k] + dp[k][j] < dp[i][j]){
                    dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
    }
}
int upgrade(int a, int b, int n){
    int answer = 0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            int first = min(dp[i][j], dp[i][a] + dp[b][j]);
            int second = min(dp[i][j], dp[i][b] + dp[a][j]);
            answer = max(answer, min(first, second));
        }
    }
    return answer;
}
void solve(){
    int n, answer = INF;
    cin>>n;

    char a;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a;
            if(a == '1'){
                dp[i][j] = 1;
            }
            else if(i != j){
                dp[i][j] = INF;
            }
            else{
                dp[i][j] = 0;
            }
        }
    }
    floydWarshall(n);

    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            answer = min(answer, upgrade(i, j, n));
        }
    }
    cout<<answer<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    
    return 0;
}