Bajtocja 是一个由 $n$ 个城市（编号从 1 到 $n$）和连接它们的双向高速公路组成的国家。在两个城市之间行驶需要消耗 1 升燃油。BajtTrans 公司的总裁 Bajtazar 对燃油消耗非常不满，因此他计划在 Bajtocja 的某两个城市之间安装一个双向传送门。传送门旅行是瞬时的，且不消耗燃油！BajtTrans 公司的卡车必须拥有足够大的油箱，以便能够在仅在起始城市加满一次油的情况下，在 Bajtocja 的任意两个城市之间行驶（城市内部消耗的燃油忽略不计，可视为微不足道）。

Bajtazar 希望最小化卡车的油箱容量。给定 Bajtocja 高速公路的描述，请在最优选择传送门连接城市的情况下，确定所需的最小油箱容量。你可以假设通过高速公路可以在任意两个城市之间通行。你需要解决 $t$ 个独立的测试用例。

输入格式

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

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 400$)，表示 Bajtocja 的城市数量。接下来的 $n$ 行描述了 Bajtocja 的高速公路。每行包含一个长度为 $n$ 的二进制字符串。第 $j$ 个字符串中的第 $i$ 个元素为 1 当且仅当存在连接城市 $i$ 和 $j$ 的高速公路。

每条高速公路连接两个不同的城市——第 $i$ 个字符串中的第 $i$ 个元素始终为 0。每条高速公路都是双向的——第 $j$ 个字符串中的第 $i$ 个元素等于第 $i$ 个字符串中的第 $j$ 个元素。通过描述的高速公路，可以在 Bajtocja 的任意两个城市之间通行。

所有测试用例的 $n$ 之和不超过 400。

输出格式

输出应包含 $t$ 行，第 $i$ 行应包含一个整数，表示在最优设置传送门的情况下，第 $i$ 个测试用例所需的最小卡车油箱容量（以升为单位）。

样例

输入 1

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

输出 1

1
2

说明 1

在第一个测试用例中，任意两个城市之间都可以通过高速公路直接到达，因此无论我们用传送门连接哪两个城市，我们仍然需要至少 1 升容量的油箱。

在第二个测试用例中，在安装传送门之前，如果油箱容量为 2 升，则无法在城市 (1, 4)、(1, 5) 和 (2, 5) 之间通行。然而，在安装传送门（例如在城市 1 和 5 之间）后，这就成为可能了。