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
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
int n;
int dist[404][404],nd[404],vv[404];
ull bs[404][7],cur[7];
vector<int> ord[404];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dist[i][j]=(i==j?0:n+2);
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		for(int j=1;j<=n;j++)
			if(s[j-1]&1)
				dist[i][j]=1;
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	for(int i=1;i<=n;i++)
	{
		ord[i].clear();
		for(int j=1;j<=n;j++)
			ord[i].push_back(j);
		sort(ord[i].begin(),ord[i].end(),[&](int a,int b){return dist[i][a]<dist[i][b];});
	}
	int l=0,r=n;
	while(l<r)
	{
		int mid=(l+r)/2;
		memset(bs,0,sizeof(bs));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				bs[i][j>>6]|=(ull)(dist[i][j]>mid)<<(j&63);
		int flag=0;
		for(int i=1;i<=n&&!flag;i++)
			for(int j=i+1;j<=n&&!flag;j++)
			{
				memset(vv,0,sizeof(vv));
				for(int a=1;a<=n;a++)
					nd[a]=min(dist[i][a],dist[j][a]);
				vector<int> vec(n+n);
				for(int a=0;a<n;a++)
				{
					vec[a]=ord[i][a];
					vec[a+n]=ord[j][a];
				}
				inplace_merge(vec.begin(),vec.begin()+n,vec.begin()+n+n,[&](int a,int b){return nd[a]<nd[b];});
				int pp=0;
				for(auto x:vec)
					if(!vv[x])
					{
						vec[pp++]=x;
						vv[x]=1;
					}
				vec.resize(pp);
				memset(cur,0,sizeof(cur));
				int ok=1;
				int p=vec.size();
				for(auto u:vec)
				{
					while(p&&nd[vec[p-1]]+nd[u]>mid)
					{
						p--;
						cur[vec[p]>>6]|=1ull<<(vec[p]&63);
					}
					for(int i=0;i<7;i++)
						if(cur[i]&bs[u][i])
						{
							ok=0;
							break;
						}
					if(!ok) break;
				}
				if(ok)
				{
					flag=1;
					break;
				}
			}
		if(flag) r=mid;
		else l=mid+1;
	}
	cout<<l<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}