题目描述

字节王国由 $n$ 个城市组成（编号从 $1$ 到 $n$），城市间通过双向高速公路相连。每经过一段高速公路需要消耗 $1$ 字节升燃料。Bajtazar 身为字节运输公司的老板，对燃料消耗颇有不满，于是计划在某两个城市间架设一个双向传送门。传送门旅行瞬时完成，且无需燃料！公司的货车油箱必须足够大，确保从起始城市一次性加满油后，能通过高速公路和传送门到达任意其他城市（城市内的燃料消耗忽略不计，微乎其微）。

Bajtazar 希望尽量缩小货车油箱容量。给定字节王国的高速公路布局，请你计算在传送门位置最优选择下的最小油箱容量。可以假设，通过高速公路网络，任意两城市间总是可达的。

你需要为 $t$ 组独立的测试数据解决这个问题。

输入格式

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 21)$，表示测试数据数量。

每组测试数据的第一行包含一个整数 $n$ $(3 \leq n \leq 400)$，表示字节王国的城市数量。接下来的 $n$ 行描述高速公路网络，每行是一个长度为 $n$ 的二进制字符串。第 $j$ 行的第 $i$ 位为 1 当且仅当城市 $i$ 和 $j$ 间存在高速公路。

• 每条高速公路连接两个不同城市（第 $i$ 行的第 $i$ 位始终为 0）。
• 高速公路是双向的（第 $j$ 行的第 $i$ 位等于第 $i$ 行的第 $j$ 位）。
• 通过高速公路网络，任意两城市间可达。

所有测试数据的 $n$ 之和不超过 $400$。

输出格式

输出 $t$ 行，每行一个整数，表示第 $i$ 组测试数据在传送门最优设置下的最小油箱容量（单位：字节升）。

2
4
0111
1011
1101
1110
5
01000
10100
01010
00101
00010

1
2

在第一组测试数据中，每对城市间都有直达高速公路，无论传送门位置，油箱容量 $1$ 字节升足够。

在第二组测试数据中，若无传送门，城市对 $(1,4)$、$(1,5)$、$(2,5)$ 需 $2$ 字节升才能到达。设置传送门（如 $1$ 和 $5$ 间）后，油箱容量 $2$ 即可覆盖所有路径。