CF1549B.Gregor and the Pawn Game

There is a chessboard of size $n$ by $n$. The square in the $i$-th row from top and $j$-th column from the left is labelled $(i,j)$.

Currently, Gregor has some pawns in the $n$-th row. There are also enemy pawns in the $1$-st row. On one turn, Gregor moves one of his pawns. A pawn can move one square up (from $(i,j)$ to $(i-1,j)$) if there is no pawn in the destination square. Additionally, a pawn can move one square diagonally up (from $(i,j)$ to either $(i-1,j-1)$ or $(i-1,j+1)$) if and only if there is an enemy pawn in that square. The enemy pawn is also removed.

Gregor wants to know what is the maximum number of his pawns that can reach row $1$?

Note that only Gregor takes turns in this game, and the enemy pawns never move. Also, when Gregor's pawn reaches row $1$, it is stuck and cannot make any further moves.

有一个 $n \times n$ 的棋盘。从上往下第 $i$ 行、从左往右第 $j$ 列的方格记为 $(i,j)$。

目前，Gregor 的一些兵位于第 $n$ 行（即最底行）。同时，敌方的兵位于第 $1$ 行（即最顶行）。在每一轮中，Gregor 移动他的一枚兵。一枚兵可以向上移动一格（即从 $(i,j)$ 移动到 $(i-1,j)$），当且仅当目标方格为空；此外，一枚兵也可以沿对角线向上移动一格（即从 $(i,j)$ 移动到 $(i-1,j-1)$ 或 $(i-1,j+1)$），当且仅当目标方格中存在一枚敌方兵；此时该敌方兵将被移除。

Gregor 想知道：他的兵最多有多少枚能够到达第 $1$ 行？

注意：本游戏中仅有 Gregor 进行回合操作，敌方兵永远不会移动。此外，当 Gregor 的一枚兵抵达第 $1$ 行后，它将被固定在该位置，无法再进行任何移动。

The first line of the input contains one integer $t$ ($1\le t\le 2\cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of three lines. The first line contains a single integer $n$ ($2\le n\le 2\cdot{10}^{5}$) — the size of the chessboard.

The second line consists of a string of binary digits of length $n$, where a $1$ in the $i$-th position corresponds to an enemy pawn in the $i$-th cell from the left, and $0$ corresponds to an empty cell.

The third line consists of a string of binary digits of length $n$, where a $1$ in the $i$-th position corresponds to a Gregor's pawn in the $i$-th cell from the left, and $0$ corresponds to an empty cell.

It is guaranteed that the sum of $n$ across all test cases is less than $2\cdot{10}^{5}$.

输入的第一行包含一个整数 $t$（$1\le t\le 2\cdot 10^4$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例由三行组成。第一行包含一个整数 $n$（$2\le n\le 2\cdot{10}^{5}$），表示棋盘的大小。

第二行是一个长度为 $n$ 的二进制数字字符串，其中第 $i$ 位上的 $1$ 表示从左往右数第 $i$ 个格子中有一个敌方兵，而 $0$ 表示该格子为空。

第三行是一个长度为 $n$ 的二进制数字字符串，其中第 $i$ 位上的 $1$ 表示从左往右数第 $i$ 个格子中有一个 Gregor 的兵，而 $0$ 表示该格子为空。

保证所有测试用例的 $n$ 值之和小于 $2\cdot{10}^{5}$。

For each test case, print one integer: the maximum number of Gregor's pawns which can reach the $1$-st row.

对于每个测试用例，输出一个整数：能够到达第 $1$ 行的 Gregor 的兵的最大数量。

In the first example, Gregor can simply advance all $3$ of his pawns forward. Thus, the answer is $3$.

In the second example, Gregor can guarantee that all $4$ of his pawns reach the enemy row, by following the colored paths as demonstrated in the diagram below. Remember, only Gregor takes turns in this "game"!

In the third example, Gregor's only pawn is stuck behind the enemy pawn, and cannot reach the end.

In the fourth example, Gregor has no pawns, so the answer is clearly $0$.

在第一个例子中，Gregor 可以简单地将他的全部 $3$ 个兵向前推进。因此，答案是 $3$。

在第二个例子中，Gregor 可以通过遵循下图中所示的彩色路径，确保他的全部 $4$ 个兵均抵达敌方底线。请注意，在这个“游戏”中，只有 Gregor 进行回合！

在第三个例子中，Gregor 唯一的一个兵被敌方兵阻挡在后方，无法抵达底线。

在第四个例子中，Gregor 没有兵，因此答案显然是 $0$。