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

Входные данные
Первая строка входного файла содержит целое число N (4 ≤ N ≤ 500). В следующих 8 строках записана матрица 8 × 8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8 × 8.

Выходные данные
Вывести в выходной файл искомое число частей.

Пример входного файла
4
0 1 0 0 0 0 1 0
1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

Пример выходного файла
11

Решение

Каждую связную область сложенного листа (если смотреть на него сверху) закодируем двоичным числом b₃b₂b₁b₀ . А именно, положим b₀ равным единице, если эта область примыкает к нижней границе листа, и нулю в противном случае. Числа b₁ , b₂ и b₃ определим аналогичным образом для верхней, правой и левой границ листа соответственно. Тем самым, все области разбиваются на 16 типов в соответствии с их кодами. Теперь проанализируем, что происходит с областями при развертывании листа. 

Рассмотрим, например, разгибание относительно нижней стороны. Легко заметить, что связная область типа b₃b₂b₁1 перейдет в связную область типа b₃b₂b₁b₁ (действительно, будет ли она прилегать к нижнему краю после разгибания зависит от того, прилегала ли она к верхнему до разгибания). Связная область типа b₃b₂b₁0 после разгибания распадется на две. Одна из них будет иметь тот же тип b₃b₂b₁0, а другая – тип b₃b₂0b₁. Аналогично анализируется разгибание листа относительно правой стороны.

Для решения задачи проделываем 2N разгибаний, обратных произведенным при складывании листа сгибаниям. При этом на каждом шаге пересчитываем количество связных областей каждого из типов.