题目描述

有一个 $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$ 行后，将无法再移动。

输入格式

输入的第一行为一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来有 $t$ 组测试数据。

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

第二行为一个长度为 $n$ 的二进制字符串，其中第 $i$ 位为 $1$ 表示第 $1$ 行第 $i$ 列有一个敌方兵，为 $0$ 表示该格为空。

第三行为一个长度为 $n$ 的二进制字符串，其中第 $i$ 位为 $1$ 表示第 $n$ 行第 $i$ 列有 Gregor 的兵，为 $0$ 表示该格为空。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示最多有多少枚 Gregor 的兵能够到达第 $1$ 行。

说明/提示

在第一个样例中，Gregor 可以直接将他的 $3$ 枚兵全部前进到第 $1$ 行，因此答案为 $3$。

在第二个样例中，Gregor 可以保证他的 $4$ 枚兵全部到达敌方所在的行，具体路径如图所示。请记住，这个“游戏”中只有 Gregor 行动！

在第三个样例中，Gregor 的唯一一枚兵被敌方兵挡住，无法到达终点。

在第四个样例中，Gregor 没有任何兵，因此答案显然为 $0$。

由 ChatGPT 4.1 翻译

样例

4
3
000
111
4
1111
1111
3
010
010
5
11001
00000

3
4
0
0