Poisonous Swamp
Contest: Kotlin Heroes: Episode 9 (Unrated, T-Shirts + Prizes!)
Difficulty rating: 1600
Tags: *special, *special, implementation, implementation

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
3
5
*..**
.**..
1
*
.
3
...
***

Example output:
2
0
2

Editorial:
View the grid the following way: first, there is a line of lily pads in the first row, then a line in the second row, and so on. Notice that you can solve the problem completely independently over these lines and sum up the answers.
So we will solve a problem for one line of lily pads with frogs of length $$$x$$$. Can all $$$x$$$ frogs survive? Well, no. In order to survive, the first frog has to jump right. So the second frog also has to jump right. So one until the last frog. It has nowhere safe to jump, so it can't survive. However, $$$x - 1$$$ is totally fine, using the same algorithm.
Thus, the task is to extract the lines from the grid, then sum up their lengths minus one. This can be calculated in a lot of ways. For my solution, I also realized that this number is equal to $$$n$$$ minus the number of lines. Or even $$$n - 1$$$ minus the number of times it changes from a lily pad to swamp or vice versa in the first row (or the second row, since these values are the same).
Overall complexity: $$$O(n)$$$ per testcase.