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

• Ціна картини, за якою вона продається, повинна бути не менша за ціну, за якою вона купувалася;
• Жоден продавець не може купити одну і ту ж картину двічі.

Деяка нова картина з'явилася на ринку, і її придбав торговець з номером 0 за ціною 0. Далі ця картина стала перепродаватися серед наявних аматорів. Вам відомі ціни, за якими торговці можуть перепродавати картину один одному. Вважаючи, що послідовність перепродаж нової картини задовольняє вище перерахованим умовам, знайдіть її максимально можливу довжину. Після виконання всіх операцій купівлі/продажу виведіть кількість людей, яке володіло картиною в будь-який момент часу, включаючи кінцевого власника і торговця з номером 0.

Вхідні дані

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

Вихідні дані

Для кожного тесту визначте найдовшу послідовність перепродаж нової картини і виведіть кількість людей, яке нею володіло включаючи кінцевого власника і торговця з номером 0. Відповіді на кожний тест слід виводити з нового рядка.