二进制字符串是由字符 $$$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$$$。