Дана шахматная доска размера \(n\) на \(n\). Клетка на пересечении \(i\)-й сверху ряду и \(j\)-го слева столбца обозначается как \((i,j)\).
На данный момент у Грегора есть несколько пешек в \(n\)-м ряду. Также в \(1\)-м ряду стоят вражеские пешки. За один шаг Грегор перемещает одну из своих пешек. Пешка может ходить на одну клетку вверх (из \((i,j)\) в \((i-1,j)\)), если клетка назначения не занята другой пешкой. В дополнение, пешка может переместиться на одну клетку вверх по диагонали (из \((i,j)\) в \((i-1,j-1)\) или в \((i-1,j+1)\)), если и только если в этой клетке стоит вражеская пешка. Вражеская пешка в таком случае убирается с доски.
Грегор хочет узнать, какое максимальное количество его пешек может достичь \(1\)-го ряда.
Заметьте, что в этой игре ходит только Грегор, вражеские пешки никогда не перемещаются. Также, когда пешка Грегора достигает \(1\)-го ряда, она останавливается и больше не может перемещаться.
Выходные данные
Для каждого набора входных данных выведите одно целое число: максимальное количество пешек Грегора, которые могут достичь \(1\)-го ряда.
Примечание
В первом примере Грегор может просто переместить вперед все его \(3\) пешки. Таким образом, ответ равен \(3\).
Во втором примере Грегор может гарантировать, что все его \(4\) пешки достигнут вражеского ряда, следуя раскрашенным путям как показано ниже. Помните — только Грегор делает ходы в этой «игре»!
В третьем примере единственная пешка Грегора застряла перед вражеской пешкой и не может достигнуть желаемого ряда.
В четвертом примере у Грегора нет пешек, поэтому ответ равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
000
111
4
1111
1111
3
010
010
5
11001
00000
|
3
4
0
0
|