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\}$）！他想对序列 $s$ 执行恰好两次下述操作，使得操作完成后对于所有 $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 \neq b_k$，则认为 $A$ 和 $B$ 是不同的。

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示两个二进制序列的长度。 第二行包含一个长度为 $n$ 的字符串 $s_1s_2 \dots s_n$ ($s_i \in \{'0', '1'\}$)，表示第一个二进制序列。 第三行包含一个长度为 $n$ 的字符串 $t_1t_2 \dots t_n$ ($t_i \in \{'0', '1'\}$)，表示第二个二进制序列。

保证所有测试数据中 $n$ 的总和不超过 $10^7$。

输出格式

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

样例

样例输入 1

3
1
1
0
2
00
11
5
01010
00111

样例输出 1

0
2
6

说明

对于第二个样例测试数据，有两个有效的操作对：$(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)$。