← 返回题目列表

Codeforces · 1566/C

C. MAX-MEX 切割

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

二进制字符串是由字符 $$$0$$$ 和 $$$1$$$ 组成的字符串。双表是恰好有两行长度相等的表,每行都是一个二进制字符串。

令双表的 $$$\operatorname{MEX}$$$ 为 $$$0$$$、$$$1$$$ 或 $$$2$$$ 中未出现在双表中的最小数字。例如,$$$\operatorname{MEX}$$$ 对于$$$\begin{bmatrix} 0011\\ 1010 \end{bmatrix}$$$ 是$$$2$$$,因为$$$0$$$ 和$$$1$$$ 在双表中至少出现一次。 $$$\operatorname{MEX}$$$ 对于 $$$\begin{bmatrix} 111\\ 111 \end{bmatrix}$$$ 是 $$$0$$$,因为 $$$0$$$ 和 $$$2$$$ 不会出现在双表中,并且 $$$0 < 2$$$。

给您一个包含 $$$n$$$ 列的双表。您应该将其切割成任意数量的双表(每个双表由连续的列组成),以便每一列恰好位于一个双表中。可以将双表切割成单个双表——整个双表。

所有结果双表的 $$$\operatorname{MEX}$$$ 的最大总和是多少?

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 双表中的列数。

接下来的两行中的每一行都包含一个长度为 $$$n$$$ 的二进制字符串 — 双表的行。

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

输出

对于每个测试用例,打印一个整数 - 通过最佳切割给定双表可以获得的所有双表的 $$$\operatorname{MEX}$$$ 的最大总和。

示例

输入 #1

4
7
0101000
1101100
5
01100
10101
2
01
01
6
000000
111111

输出 #1

8
8
2
12

注意

在第一个测试用例中,您可以按如下方式剪切双表:

- $$$\begin{bmatrix} 0\\ 1 \end{bmatrix}$$$,其$$$\operatorname{MEX}$$$为$$$2$$$。
- $$$\begin{bmatrix} 10\\ 10 \end{bmatrix}$$$,其$$$\operatorname{MEX}$$$为$$$2$$$。
- $$$\begin{bmatrix} 1\\ 1 \end{bmatrix}$$$,其$$$\operatorname{MEX}$$$为$$$0$$$。
- $$$\begin{bmatrix} 0\\ 1 \end{bmatrix}$$$,其$$$\operatorname{MEX}$$$为$$$2$$$。
- $$$\begin{bmatrix} 0\\ 0 \end{bmatrix}$$$,其$$$\operatorname{MEX}$$$为$$$1$$$。
- $$$\begin{bmatrix} 0\\ 0 \end{bmatrix}$$$,其$$$\operatorname{MEX}$$$为$$$1$$$。

$$$\operatorname{MEX}$$$ 的总和为 $$$8$$$。