← 返回题目列表

Codeforces · 1549/B

B. 格雷戈尔和典当游戏

中文机器翻译题面 查看原题

有一个棋盘,尺寸为 $$$n$$$,乘以 $$$n$$$。从上起第 $$$i$$$ 行和从左起第 $$$j$$$ 列中的正方形标记为 $$$(i,j)$$$。

目前,Gregor 在第 $$$n$$$ 行中有一些棋子。 $$$1$$$-st 行中也有敌人的棋子。在一回合中,格雷戈尔移动了他的一个棋子。如果目标方格中没有棋子,则棋子可以向上移动一个方格(从 $$$(i,j)$$$ 到 $$$(i-1,j)$$$)。此外,当且仅当该方格中有敌方棋子时,棋子才可以沿对角线向上移动一个方格(从 $$$(i,j)$$$ 到 $$$(i-1,j-1)$$$ 或 $$$(i-1,j+1)$$$)。敌人的棋子也被移除。

Gregor 想知道他的棋子最多可以到达 $$$1$$$ 行?

请注意,在这个游戏中只有格雷戈尔轮流,而敌人的棋子永远不会移动。此外,当 Gregor 的棋子到达 $$$1$$$ 行时,它被卡住并且无法进行任何进一步的移动。

输入

输入的第一行包含一个整数 $$$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}$$$。

输出

对于每个测试用例,打印一个整数:可以到达 $$$1$$$-st 行的 Gregor 棋子的最大数量。

示例

输入 #1

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

输出 #1

3
4
0
0

注意

在第一个例子中,Gregor 可以简单地将所有 $$$3$$$ 的棋子向前推进。因此,答案是$$$3$$$。

在第二个示例中,Gregor 可以通过遵循下图所示的彩色路径,保证他的所有 $$$4$$$ 棋子到达敌方行。请记住,只有格雷戈尔轮流参加这个“游戏”!

在第三个示例中,Gregor 唯一的棋子卡在敌人棋子的后面,无法到达终点。

在第四个例子中,Gregor 没有棋子,所以答案显然是 $$$0$$$。