Bajtocja 是一個由 $n$ 個城市（編號從 $1$ 到 $n$）以及連接它們的雙向高速公路組成的國家。在兩個城市之間行駛需要消耗 $1$ 個 bajtolitr 的燃料。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$ 個測試案例中，設置最佳傳送門後卡車所需的最小油箱容量（以 bajtolitr 為單位）。

範例

範例輸入 1

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

範例輸出 1

1
2

說明

在第一個測試案例中，任意兩個城市之間都可以直接透過高速公路到達，因此無論我們用傳送門連接哪兩個城市，我們仍然需要容量至少為 $1$ bajtolitr 的油箱。

在第二個測試案例中，在設置傳送門之前，若油箱容量為 $2$ bajtolitr，則無法在城市對 $(1, 4)$、$(1, 5)$ 以及 $(2, 5)$ 之間通行。然而，在設置傳送門後（例如連接城市 $1$ 和 $5$），這就變為可能了。