Description

DreamGrid 刚刚从他的虚拟机中找到了两个二进制序列 $s_1, s_2, \dots, s_n$ 和 $t_1, t_2, \dots, t_n$（对于所有 $1 \le i \le n$，$s_i, t_i \in \{0, 1\}$）！他想要执行下面描述的操作恰好两次，使得在两次操作后，对于所有 $1 \le i \le n$，都有 $s_i = t_i$。 操作是：选择两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），将所有 $l \le i \le r$ 的 $s_i$ 变为 $(1 - s_i)$。 DreamGrid 想知道有多少种方法可以做到这一点。 我们使用以下规则来确定两种方法是否不同： - 设 $A = (a_1, a_2, a_3, a_4)$，其中 $1 \le a_1 \le a_2 \le n, 1 \le a_3 \le a_4 \le n$，表示 DreamGrid 为第一次操作选择整数 $a_1$ 和 $a_2$，为第二次操作选择整数 $a_3$ 和 $a_4$； - 设 $B = (b_1, b_2, b_3, b_4)$，其中 $1 \le b_1 \le b_2 \le n, 1 \le b_3 \le b_4 \le n$，表示 DreamGrid 为第一次操作选择整数 $b_1$ 和 $b_2$，为第二次操作选择整数 $b_3$ 和 $b_4$。 - 如果存在整数 $k$（$1 \le k \le 4$）使得 $a_k e b_k$，则 $A$ 和 $B$ 被认为是不同的。

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示两个二进制序列的长度。 第二行包含一个长度为 $n$ 的字符串 $s_1s_2\dots s_n$（$s_i \in \{\text{`0'}, \text{`1'}\}$），表示第一个二进制序列。 第三行包含一个长度为 $n$ 的字符串 $t_1t_2\dots t_n$（$t_i \in \{\text{`0'}, \text{`1'}\}$），表示第二个二进制序列。 保证所有测试用例中 $n$ 的总和不超过 $10^7$。

Output Format

对于每个测试用例，输出一个整数表示答案。

3
1
1
0
2
00
11
5
01010
00111

0
2
6

Hint

对于第二个样例测试用例，有两个有效的操作对：$(1, 1, 2, 2)$ 和 $(2, 2, 1, 1)$。 对于第三个样例测试用例，有六个有效的操作对：$(2, 3, 5, 5)$，$(5, 5, 2, 3)$，$(2, 5, 4, 4)$，$(4, 4, 2, 5)$，$(2, 4, 4, 5)$ 和 $(4, 5, 2, 4)$。

题面翻译由 ChatGPT-4o 提供。