310924: CF1910C. Poisonous Swamp

C. Poisonous Swamptime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The first location in the brand new critically acclaimed fantasy action RPG "Ancient Staff" is a poisonous swamp. The swamp has some lily pads growing in it. It can be represented as a $2 \times n$ grid ($2$ rows and $n$ columns), where each cell is either empty or has a lily pad in it.

There are exactly $n$ lily pads in a swamp — one in each column. A frog is sitting on top of every lily pad. In one move, every frog must jump to an adjacent by a side cell.

After the move, no frog can be outside the grid and no two frogs can share the same lily pad. Two frogs from adjacent cells can't jump towards each other (i.e. swap cells).

If a frog jumps to a lily pad, it survives. Otherwise, it falls into a poisonous swamp and gets devoured by an eldritch creature living on its bottom.

You can choose the direction each frogs jumps at. Determine the maximum number of frogs that can survive after one move.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of the testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of columns in a swamp grid.

Each of the following two lines contains a description of a row of a swamp — a string, consisting of exactly $n$ characters. Each character is either a dot ('.'), denoting a swamp cell, or an asterisk ('*'), denoting a lily pad with a frog.

In each column, there is exactly one dot and exactly one asterisk. The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.

Output

For each testcase, print a single integer — the maximum number of frogs that can survive after one move, if you choose the direction each frogs jumps at.

ExampleInput

3
5
*..**
.**..
1
*
.
3
...
***

Output

2
0
2

Note

The $i$-th frog is the frog on the lily pad in the $i$-th column.

In the first testcase:

• the first frog can't survive because there's no adjacent lily pad;
• the second and the third frogs can jump right and up, respectively, — there's no way to save them both at the same time;
• the fourth and the fifth frogs can jump left and left, respectively, — there's no way to save them both at the same time; note, however, that the third and the fourth frogs will end up in the same cell in the swamp, which is not prohibited.

题目大意：
在幻想动作RPG游戏“远古法杖”的第一个场景中，有一个有毒的沼泽地，上面长着一些荷叶。沼泽可以表示为一个2×n的网格（2行n列），每个单元格要么为空，要么有一个荷叶。每个荷叶上都有一只青蛙。在一次移动中，每只青蛙必须跳到旁边的一个单元格。移动后，没有青蛙可以在网格外面，且没有两只青蛙可以共享同一个荷叶。相邻单元格的两只青蛙不能互相跳（即交换位置）。如果青蛙跳到一个荷叶上，它就会存活；否则，它会掉进有毒的沼泽并被底部的怪异生物吞噬。你可以选择每只青蛙的跳跃方向。确定一次移动后可以存活的青蛙的最大数量。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——沼泽网格中的列数。
接下来的两行各包含n个字符，分别代表沼泽的两行。每个字符要么是点（'.'），表示沼泽单元格，要么是星号（'*'），表示带有青蛙的荷叶。
每一列恰好有一个点和一颗星号。所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，打印一个整数——如果你可以选择每只青蛙的跳跃方向，一次移动后可以存活的青蛙的最大数量。

示例：
输入：
3
5
*..**
.**..
1
*
.
3
...
***

输出：
2
0
2

注意：
第i只青蛙是位于第i列荷叶上的青蛙。
在第一个测试用例中：
- 第一只青蛙不能存活，因为没有相邻的荷叶；
- 第二只和第三只青蛙可以分别向右和向上跳，无法同时救它们两个；
- 第四只和第五只青蛙可以分别向左和向左跳，无法同时救它们两个；但是要注意，第三只和第四只青蛙最终会跳到沼泽的同一个单元格，这是允许的。题目大意： 在幻想动作RPG游戏“远古法杖”的第一个场景中，有一个有毒的沼泽地，上面长着一些荷叶。沼泽可以表示为一个2×n的网格（2行n列），每个单元格要么为空，要么有一个荷叶。每个荷叶上都有一只青蛙。在一次移动中，每只青蛙必须跳到旁边的一个单元格。移动后，没有青蛙可以在网格外面，且没有两只青蛙可以共享同一个荷叶。相邻单元格的两只青蛙不能互相跳（即交换位置）。如果青蛙跳到一个荷叶上，它就会存活；否则，它会掉进有毒的沼泽并被底部的怪异生物吞噬。你可以选择每只青蛙的跳跃方向。确定一次移动后可以存活的青蛙的最大数量。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——沼泽网格中的列数。 接下来的两行各包含n个字符，分别代表沼泽的两行。每个字符要么是点（'.'），表示沼泽单元格，要么是星号（'*'），表示带有青蛙的荷叶。 每一列恰好有一个点和一颗星号。所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，打印一个整数——如果你可以选择每只青蛙的跳跃方向，一次移动后可以存活的青蛙的最大数量。 示例： 输入： 3 5 *..** .**.. 1 * . 3 ... *** 输出： 2 0 2 注意： 第i只青蛙是位于第i列荷叶上的青蛙。 在第一个测试用例中： - 第一只青蛙不能存活，因为没有相邻的荷叶； - 第二只和第三只青蛙可以分别向右和向上跳，无法同时救它们两个； - 第四只和第五只青蛙可以分别向左和向左跳，无法同时救它们两个；但是要注意，第三只和第四只青蛙最终会跳到沼泽的同一个单元格，这是允许的。