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