假设有两个长度均为 $M$ 的数组 $X$ 和 $Y$。你可以进行任意多次以下操作：

• 选择一个索引 $i$（$1 \le i \le M$），并交换 $X_i$ 和 $Y_i$。

如果可以通过进行若干次此类交换使得它们的前缀 MEX 数组相等，则称数对 $(X, Y)$ 是好的。

一个整数集合的 MEX 是指未在该集合中出现的最小非负整数。

一个数组 $Z$ 的前缀 MEX 数组是一个与 $Z$ 长度相同的数组 $P$，满足对于每个 $1 \le i \le |Z|$：

$$P_i = \text{MEX}(Z_1, Z_2, \dots, Z_i)$$

给定两个长度均为 $N$ 的数组 $A$ 和 $B$。 统计满足 $1 \le L \le R \le N$ 且子数组对

$$(A_L, A_{L+1}, \dots, A_R) \quad \text{和} \quad (B_L, B_{L+1}, \dots, B_R)$$

是好的的数对 $(L, R)$ 的数量。

输入格式

输入格式如下：

$$T$$ $$N$$ $$A_1\ A_2\ \dots\ A_N$$ $$B_1\ B_2\ \dots\ B_N$$ $$\vdots$$

数据范围

• 所有输入值均为整数。
• $1 \le T \le 10^5$
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le N$
• $0 \le B_i \le N$
• 保证所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示满足 $1 \le L \le R \le N$ 且子数组对 $(A_L, \dots, A_R)$ 和 $(B_L, \dots, B_R)$ 是好的的数对 $(L, R)$ 的数量。

样例

输入 1

3
4
0 2 1 0
0 1 0 2
3
1 2 1
2 1 1
4
0 0 3 1
2 0 1 1

输出 1

2
6
4

说明

测试用例 1：满足条件的数对为 $(1, 1)$ 和 $(2, 2)$。

测试用例 2：所有数对均满足条件。

测试用例 3：满足条件的数对为 $(2, 2)$、$(3, 3)$、$(4, 4)$ 和 $(3, 4)$。