D. Good Schedule

Alice and Bob decided to watch a TV series consisting of $n$ episodes, numbered from $1$ to $n$. The series will be shown on television over the next $n$ days. Unfortunately, they live in different cities, and the episode schedules may differ. On the $i$-th day, the $a_i$-th episode will be shown in Alice's city, and the $b_i$-th episode in Bob's city.

They plan to select a segment of days $[L, R]$ ($1 \le L \le R \le n$) to watch the series. Initially, neither of them has seen any episodes. Each day $i$ in this segment, the following happens:

• if Alice has already watched episodes $1, 2, \dots, a_i-1$, but not $a_i$, then she watches $a_i$ on day $i$; otherwise, she watches nothing on this day;

• if Bob has already watched episodes $1, 2, \dots, b_i-1$, but not $b_i$, then he watches $b_i$ on day $i$; otherwise, he watches nothing on this day. To avoid spoilers in their conversations, Alice and Bob want to choose a segment $[L, R]$ such that on every day in this segment, one of the following holds:

• either they both watch the same episode on that day;

• or neither of them watches anything on that day. Help Alice and Bob calculate the number of suitable segments $[L, R]$.

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$);
• the third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$). Additional constraint on the input: the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

For each test case, print a single integer — the number of suitable segments $[L, R]$.

ExampleNoteIn the first example, the suitable segments are $[1, 1]$, $[1, 2]$, $[1, 3]$, and $[2, 2]$.

Input

InputThe first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$);
• the third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$). Additional constraint on the input: the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

OutputFor each test case, print a single integer — the number of suitable segments $[L, R]$.

Samples

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

6
1
6

Note

NoteIn the first example, the suitable segments are $[1, 1]$, $[1, 2]$, $[1, 3]$, and $[2, 2]$.