题目描述

一个二进制字符串是只包含字符 $0$ 和 $1$ 的字符串。一个“二表”是一个有且仅有两行、长度相等且每行都是二进制字符串的表格。

定义“二表”的 $\operatorname{MEX}$ 为 $0$、$1$、$2$ 中未在该二表中出现的最小数字。例如，$\begin{bmatrix} 0011\\ 1010 \end{bmatrix}$ 的 $\operatorname{MEX}$ 是 $2$，因为 $0$ 和 $1$ 都至少出现过一次。$\begin{bmatrix} 111\\ 111 \end{bmatrix}$ 的 $\operatorname{MEX}$ 是 $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}$ 之和的最大值。

说明/提示

在第一个测试用例中，可以按如下方式切分二表：

• $\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$。

由 ChatGPT 4.1 翻译

样例

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

8
8
2
12