Первая локация в новейшей фэнтези ролевой игре «Ancient Staff» — это ядовитое болото. В болоте растут кувшинки. Его можно представить как сетку \(2 \times n\) (\(2\) строки и \(n\) столбцов), где каждая ячейка либо пустая, либо содержит кувшинку.
В болото ровно \(n\) кувшинок — по одной в каждом столбце. На каждой кувшинке сидит лягушка. За один ход лягушка обязана прыгнуть в соседнюю по стороне ячейку.
После хода никакая лягушка не может оказаться за границей сетки, и никакие две лягушки не могут находиться на одной кувшинке. Две лягушки из соседних не могут прыгать навстречу друг другу (то есть меняться ячейками).
Если лягушка прыгает на кувшинку, то она выживает. Иначе она попадает в ядовитое болото, и ее поглощает древнее существо, живущее на его дне.
Вы можете выбирать, в каком направлении прыгает каждая лягушка. Определите наибольшее количество лягушек, которые могут выжить после одного хода.
Выходные данные
На каждый набор входных данных выведите одно целое число — наибольшее количество лягушек, которые могут выжить после одного хода, если вы выберете направление для прыжка каждой лягушке.
Примечание
\(i\)-я лягушка — это лягушка на кувшинке в \(i\)-м столбце.
В первом наборе входных данных:
- первая лягушка не может выжить, потому что нет соседних кувшинок;
- вторая и третья лягушки могут прыгнуть вправо и наверх, соответственно, — их обеих одновременно спасти не получится;
- четвертая и пятая лягушки могут прыгнуть влево и влево, соответственно, — их обеих одновременно спасти не получится; обратите внимание, однако, что третья и четвертая лягушки окажутся в одной ячейке с болотом, что не запрещено.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
*..**
.**..
1
*
.
3
...
***
|
2
0
2
|