题目描述

给你一个竞赛图，令 $\mathrm{dist}(u,v)$ 表示从 $u$ 走到 $v$ 的最短路，如果无法从 $u$ 走到 $v$ 则为 $10^9$。 求 $\min_{1\le u \le n} \max_{1\le v \le n} \mathrm{dist}(u, v)$。

输入格式

第一行是输入一个 $T$， 接下来 $T$ 组数据。 每组数据第一行一个 $n$，接下来 $n$ 行长度为 $n$ 的 01 串 $a_{i,j}$，表示是否有 $i$ 到 $j$ 的有向边。

保证 $a_{i,i} = 0, \forall i\not=j, a_{i,j}+a_{j,i} = 1$。

输出格式

输出 $T$ 行，每行一个答案。

样例输入 1

2
4
0101
0000
1101
0100
5
01100
00010
01000
10101
11100

样例输出 1

1
2

数据范围

保证 $1 \le n \le 10000, a_{i, j} \in \{0, 1\}$。

时间限制：1s

空间限制：1GB