Сегодня Максиму не повезло в игре в "Морской бой". Играя с соседом по парте, он ни разу не попал ни в один корабль противника. Игра продолжалась до тех пор, пока Марь Иванна не увидела, что ребята заняты на уроке не тем, чем надо. Игру пришлось закончить досрочно победой соседа. Прийдя домой, Максим решил определить, какой максимальной длины корабль мог быть у противника.
Но теперь его отвлекла мама и позвала ужинать. Он ушел ужинать и попросил вас помочь ему найти ответ.
Морской бой представляет из себя игру на клетчатом поле размером 10 x 10 клеток. Максим успел прислать вам поле прошедшей игры. На поле отмечены клетки, в которые Максим уже стрелял. На поле можно размещать корабли любого размера, но обязательное условие, чтобы корабль был прямоугольным с шириной, равной 1. Располагать корабль разрешается либо горизонтально либо вертикально.
Входные данные
На вход программа получает 10 строк по 10 чисел в каждой, числа разделены пробелами. Число 1 означает, что в соответствующую клетку стреляли, число 0 – что в клетку не стреляли.
(Гарантируется, что на поле есть хотя бы одна небитая клетка.)
Выходные данные
Выведите ответ – максимальную возможную длину корабля.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0
|
10
|