Задача составлена по мотивам известной игры «Жизнь» Дж. Конуэя.

Поле в «Хитрой жизни» – ограниченная плоская треугольная решетка:

Решетка состоит ровно из 100 ячеек – в точности, как на рисунке. Соседями ячейки будем считать другие ячейки, имеющие с данной либо общую границу, либо общую вершину. Любая ячейка имеет не более 12 соседей. Ячейки, близкие к границе поля, имеют разное число соседей.

Каждая ячейка может находиться в двух состояниях: быть «живой» (1) или «мёртвой» (0).

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

• в мёртвой ячейке, с которой соседствуют 3 либо 4 живые ячейки, зарождается жизнь (0 меняется на 1);

• если у живой ячейки есть 2-5 живых соседей, то эта клетка продолжает жить (1 остается 1);

• в противном случае (если живых соседей меньше 2 или больше 5) ячейка умирает (либо «от одиночества», либо «от перенаселённости») (1 меняется на 0). Важно, что гибель и рождение всех ячеек на каждом шаге эволюции происходят одновременно!

«Хитрая жизнь» может «замереть», если на поле не останется ни одной живой ячейки, либо при очередном шаге эволюции ни одна из ячеек не будет менять своего состояния.

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

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

Начальное состояние решетки (нулевое поколение) должно считываться из стандартного потокаа ввода в котором содержится ровно 10 строк. В каждой строке (через пробел) записаны единички и нолики – состояния ячеек для полосок решетки (слева направо). Для однозначности ячейки будут нумероваться в том же порядке, как на рисунке. Далее идет еще одна строка, содержаащая одно целое число N \((1 ≤ N ≤ 10^6)\) – номер поколения, для которого моделируется ответ.

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

Целое число – количество живых ячеек на решетке.

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

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 0 0
0 0 1 0 1 0 1 0 0 0
0 0 0 1 0 1 0 1 0 0
0 0 1 0 1 0 1 0 0 0
0 0 0 1 0 1 0 1 0 0
0 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10

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

53