Байтоция — это страна, состоящая из $n$ городов (пронумерованных числами от 1 до $n$) и соединяющих их двусторонних автомагистралей. Проезд по автомагистрали между двумя городами требует расхода одного байтолитра топлива. Байтазар, президент компании BajtTrans, очень недоволен расходом топлива, поэтому он планирует разместить двусторонний телепорт между какими-то двумя городами Байтоции. Путешествие через телепорт происходит мгновенно и не требует топлива! Грузовики компании BajtTrans должны иметь достаточно большой топливный бак, чтобы иметь возможность проехать между любой парой городов Байтоции на одной заправке в начальном городе (топливом, расходуемым внутри каждого из городов, можно пренебречь, так как оно ничтожно мало).

Байтазар хотел бы минимизировать размер бака грузовиков. Имея описание автомагистралей Байтоции, определите минимально необходимый размер бака при условии, что пара городов, соединенных телепортом, будет выбрана оптимально. Вы можете считать, что, используя автомагистрали, можно проехать между любой парой городов. Вам необходимо решить эту задачу для $t$ независимых тестовых случаев.

Входные данные

В первой строке входных данных находится число $t$ ($1 \le t \le 21$), обозначающее количество тестовых случаев.

В первой строке описания каждого тестового случая находится число $n$ ($3 \le n \le 400$), обозначающее количество городов в Байтоции. Следующие $n$ строк тестового случая содержат описание автомагистралей в Байтоции. В каждой из них находится бинарная строка длины $n$. $i$-й элемент в $j$-й строке равен 1 тогда и только тогда, когда существует автомагистраль, соединяющая города с номерами $i$ и $j$.

Каждая автомагистраль соединяет два различных города — $i$-й элемент в $i$-й строке всегда равен 0. Каждая автомагистраль двусторонняя — $i$-й элемент в $j$-й строке равен $j$-му элементу в $i$-й строке. Используя описанные автомагистрали, можно проехать между любой парой городов в Байтоции.

Сумма $n$ по всем тестовым случаям не превышает 400.

Выходные данные

На выходе должно быть $t$ строк, в $i$-й из которых должно находиться одно целое число, обозначающее минимальный размер бака грузовика (в байтолитрах) при оптимальной установке телепорта для $i$-го тестового случая.

Примеры

Пример 1

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

Пример 2

1
2

Примечание

В первом тестовом случае между любой парой городов можно проехать напрямую по автомагистрали, и независимо от того, какие города мы соединим телепортом, нам все равно потребуется бак емкостью не менее 1 байтолитра.

Во втором тестовом случае до установки телепорта с баком емкостью два байтолитра невозможно проехать между городами с номерами (1, 4); (1, 5) и (2, 5). Однако после установки телепорта (например, между городами с номерами 1 и 5) это становится возможным.