B. CoCo Count
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$, each of size $$$n$$$.

Count the number of good subarrays $$$[l,r]$$$.

A subarray $$$[l,r]$$$ is considered good if the following two conditions hold:

  • the length of the subarray is greater than or equal to 2.
  • $$$a_l$$$ exists in the set $$${b_l, b_{l+1},\cdots, b_r}$$$.
  • $$$a_r$$$ doesn't exist in the set $$${b_l, b_{l+1},\cdots, b_r}$$$.
Input

The first line of the input contains one single integer $$$tc$$$ $$$(1 \le tc \le 10^5)$$$ — the number of test cases.

The first line of each test case contains one single integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — the length of the array.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — the array $$$a$$$.

The third line contains $$$n$$$ integers $$$b_i$$$ $$$(1 \le b_i \le 10^9)$$$ — the array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each test case print the number of good subarrays.

Example
Input
2
3
1 3 2
2 1 3
5
1 2 3 4 5
5 4 3 2 1
Output
2
3