|
В заповеднике растет роща реликтовых деревьев. Для защиты растений требуется обнести их забором. Но для обеспечения доступа к остальной территории заповедника площадь участка, окруженного забором, должна быть минимальной. Деревья растут точно в узлах координатной сетки на расстоянии 1 метра друг от друга. Причем любое из деревьев имеет хотя бы одного соседа (с юга, севера, востока или запада). Забор состоит из блоков длиной в 1 метр. Чтобы огородить 1 дерево, необходимо 4 блока забора:
Чтобы огородить такую группу из 9 деревьев, нужно 20 блоков:
Требуется написать программу, которая по заданной конфигурации рощи определит минимально необходимое число блоков для забора.
Исходные данные
В первой строке записано одно число N - количество строк данных. В следующих N строках содержатся последовательности из K символов (единиц или нулей). Единицей обозначается расположение реликтового дерева, а нулем - его отсутствие в узле координатной сетки.
1<=N,K<=40.
Результат
Выведите число блоков забора, необходимое для огораживания.
Пример
| Исходные данные | Результат |
|---|
3
001110
011011
011110
|
16
|
4
0000000000
0000000000
0000000000
0000000000
|
0
|
| 
