バイトシアは $n$ 個の都市（$1$ から $n$ までの番号が付けられている）と、それらを結ぶ双方向の高速道路からなる国です。2つの都市間の高速道路を移動するには、1バイトリットルの燃料を消費します。バイトシアの運送会社BajtTransの社長であるバイトザールは、燃料消費に非常に不満を抱いており、バイトシアの任意の2都市間に双方向のテレポートを設置することを計画しています。テレポートによる移動は瞬時に行われ、燃料を消費しません！BajtTransのトラックは、出発地の都市で一度給油すれば、バイトシアのどの2都市間でも移動できるように、十分な大きさの燃料タンクを備えている必要があります（各都市内での燃料消費は無視できるほど少ないため考慮しません）。

バイトザールは、トラックの燃料タンクのサイズを最小化したいと考えています。バイトシアの高速道路の記述が与えられたとき、テレポートで結ぶ2都市のペアを最適に選択したと仮定して、必要な最小の燃料タンクサイズを求めてください。高速道路を使ってどの2都市間も移動可能であると仮定して構いません。この問題を $t$ 個の独立したテストケースについて解く必要があります。

入力

入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 21$) が含まれます。 各テストケースの最初の行には、バイトシアの都市の数 $n$ ($3 \le n \le 400$) が含まれます。続く $n$ 行には、バイトシアの高速道路の記述が含まれます。各行は長さ $n$ のバイナリ文字列です。$j$ 番目の文字列の $i$ 番目の要素は、都市 $i$ と都市 $j$ を結ぶ高速道路が存在する場合に限り $1$ となります。

各高速道路は異なる2つの都市を結び、$i$ 番目の文字列の $i$ 番目の要素は常に $0$ です。各高速道路は双方向であり、$j$ 番目の文字列の $i$ 番目の要素は $i$ 番目の文字列の $j$ 番目の要素と等しくなります。記述された高速道路を使用して、バイトシアのどの2都市間も移動可能です。

すべてのテストケースにおける $n$ の合計は $400$ を超えません。

出力

出力には $t$ 行を含める必要があります。$i$ 番目の行には、$i$ 番目のテストケースにおいてテレポートを最適に設置したときの、トラックの最小燃料タンクサイズ（バイトリットル単位）を表す整数を1つ出力してください。

入出力例

入力 1

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

出力 1

1
2

注記

例の解説：最初のテストケースでは、どの2都市間も高速道路で直接移動できるため、どの都市間にテレポートを設置しても、少なくとも1バイトリットルの容量のタンクが必要です。

2番目のテストケースでは、テレポートを設置する前は、容量2バイトリットルのタンクでは都市のペア (1, 4)、(1, 5)、および (2, 5) の間を移動できません。しかし、テレポートを設置した後（例えば都市1と都市5の間）は、移動が可能になります。