Общество любителей искусства известно тем, что его члены время от времени продают и покупают картины друг у друга. Каждая продажа картины происходит согласно следующим правилам:

• Цена картины, по которой она продается, должна быть не меньше цены, по которой она покупалась;
• Ни один продавец не может купить одну и ту же картину дважды.

Некая новая картина появилась на рынке, и ее приобрел торговец с номером 0 по цене 0. Далее эта картина стала перепродаваться среди имеющихся любителей. Вам известны цены, по которым торговцы могут перепродавать картину друг другу. Считая, что последовательность перепродаж новой картины удовлетворяет выше перечисленным условиям, найдите ее максимально возможную длину. После выполнения всех операций покупки/продажи выведите количество людей, которое владело картиной в любой момент времени, включая конечного владельца и торговца с номером 0.

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

Состоит из нескольких тестов, каждый из которых имеет следующую структуру. Первая строка содержит количество торговцев картин n (2 ≤ n ≤ 15). Каждая из следующих n строк содержит n цифр. Они описывают матрицу стоимостей, где j-ый символ i-ой строки содержит цифру - стоимость, за которую торговец j купит картину у торговца i. Известно, что 0 является наименьшей ценой, а 9 наибольшей.

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

Для каждого теста определите самую длинную последовательность перепродаж новой картины и выведите количество людей, которое ею владело включая конечного владельца и торговца с номером 0. Ответы на каждый тест следует выводить с новой строки.