Make Three Regions
Contest: Educational Codeforces Round 168 (Rated for Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, two pointers

There is a grid, consisting of $$$2$$$ rows and $$$n$$$ columns. Each cell of the grid is either free or blocked.

A free cell $$$y$$$ is reachable from a free cell $$$x$$$ if at least one of these conditions holds:

- $$$x$$$ and $$$y$$$ share a side;
- there exists a free cell $$$z$$$ such that $$$z$$$ is reachable from $$$x$$$ and $$$y$$$ is reachable from $$$z$$$.

A connected region is a set of free cells of the grid such that all cells in it are reachable from one another, but adding any other free cell to the set violates this rule.

For example, consider the following layout, where white cells are free, and dark grey cells are blocked:

There are $$$3$$$ regions in it, denoted with red, green and blue color respectively:

The given grid contains at most $$$1$$$ connected region. Your task is to calculate the number of free cells meeting the following constraint:

- if this cell is blocked, the number of connected regions becomes exactly $$$3$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of columns.

The $$$i$$$-th of the next two lines contains a description of the $$$i$$$-th row of the grid — the string $$$s_i$$$, consisting of $$$n$$$ characters. Each character is either . (denoting a free cell) or x (denoting a blocked cell).

Additional constraint on the input:

- the given grid contains at most $$$1$$$ connected region;
- the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the number of cells such that the number of connected regions becomes $$$3$$$ if this cell is blocked.

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

Note:
In the first test case, if the cell $$$(1, 3)$$$ is blocked, the number of connected regions becomes $$$3$$$ (as shown in the picture from the statement).

Example input:
4
8
.......x
.x.xx...
2
..
..
3
xxx
xxx
9
..x.x.x.x
x.......x

Example output:
1
0
0
2

Editorial:
Since the chosen cell should split a connected region into $$$3$$$ non-empty parts, this cell should share a side with all $$$3$$$ of them. But any cell has at most $$$3$$$ neighbor cells (because there are only $$$2$$$ rows), and they should be split from each other by blocked cells.
From the above, we can conclude how a pattern of a "good" cell should look like. In fact, there are only $$$2$$$ of them (on the layouts below, white cells are free, dark grey cells are blocked, and the red cell is a "good" cell):
These patterns are the only possible ones: all $$$3$$$ neighbors of a "good" cell should be free (otherwise there will be less than $$$3$$$ regions connected to it); and both of the "corner" cells should be blocked (if at least one of them is free, two regions will merge into one, so there will be less than $$$3$$$ regions).
So the problem becomes to calculate the number of the above patterns inside the given grid.