C. Ядовитое болото
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Первая локация в новейшей фэнтези ролевой игре «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$$$.

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

На каждый набор входных данных выведите одно целое число — наибольшее количество лягушек, которые могут выжить после одного хода, если вы выберете направление для прыжка каждой лягушке.

Пример
Входные данные
3
5
*..**
.**..
1
*
.
3
...
***
Выходные данные
2
0
2
Примечание

$$$i$$$-я лягушка — это лягушка на кувшинке в $$$i$$$-м столбце.

В первом наборе входных данных:

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