Gregor and the Pawn Game

题意翻译

现在在一个 $n \times n$ 的棋盘上，最上方一行有一些对手的兵，最下方一行有一些我方的兵（均用 $1$ 表示有兵，$0$ 表示没有兵）。对手的兵不会动，我方的兵可以移动，移动规则如下。 对于位于 $(x,y)$ 的我方的兵： 如果 $(x-1,y)$ 没有兵，则该兵可以向上走到 $(x-1,y)$。 如果 $(x-1,y+1)$ 或 $(x-1,y+1)$ 有敌方的兵，那你可以把敌方的兵移出棋盘并斜向上走到它的位置。 问通过若干次移动，最多可以使多少我方的兵到达最上方一行？

题目描述

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.

输入输出格式

输入格式

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} $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

3
4
0
0

说明

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 $ .