D. Symmetric Swap
time limit per test
4.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For an array of integers $$$c_1, c_2, \ldots, c_n$$$, you can transform it by performing the following operation any number of times (including zero):

  • Select an integer $$$\ell$$$ such that $$$1 \leq \ell \leq \lfloor \frac{n}{2} \rfloor$$$. Then, swap the prefix of length $$$\ell$$$ with the suffix of length $$$\ell$$$.

For example, if $$$c = [1, 2, 3, 4, 5, 6]$$$ of length $$$6$$$, you can select $$$\ell$$$ such that $$$1 \leq \ell \leq \lfloor \frac{6}{2} \rfloor = 3$$$. If you select $$$\ell = 2$$$, you swap the prefix $$$[1, 2]$$$ with the suffix $$$[5, 6]$$$, resulting in $$$[5, 6, 3, 4, 1, 2]$$$.

Let $$$f(c, i)$$$ denote the $$$i$$$-th left cyclic shift of array $$$c$$$. That is, $$$f(c, i) = [c_{i + 1}, c_{i+2}, \ldots, c_{n}, c_1, c_2, \ldots, c_i]$$$. For example, if $$$c = [1, 2, 3, 4, 5, 6]$$$, then $$$f(c, 2) = [3, 4, 5, 6, 1, 2]$$$.

You are given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$. Your task is to find the number of pairs of integers $$$(i, j)$$$ where $$$0 \leq i, j \lt n$$$ such that $$$f(a, i)$$$ can be transformed into $$$f(b, j)$$$ using the aforementioned operations.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — the length of both arrays.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — the elements of array $$$a$$$.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^6$$$) — the elements of array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the number of pairs of integers $$$(i, j)$$$ where $$$0 \leq i, j \lt n$$$ such that $$$f(a, i)$$$ can be transformed into $$$f(b, j)$$$.

Example
Input
2
3
1 2 3
2 1 3
2
1 1
1 1
Output
3
4
Note

In the first test case, as $$$n = 3$$$, so you can select $$$\ell$$$ such that $$$1 \leq \ell \leq \lfloor \frac{3}{2} \rfloor = 1$$$. It can be shown that there are $$$3$$$ valid pairs for this case. For example, $$$(1, 1)$$$ is a valid pair, as $$$f(a, 1) = [2, 3, 1]$$$ can be transformed to $$$f(b, 1) = [1, 3, 2]$$$ by swapping the prefix $$$[2]$$$ with the suffix $$$[1]$$$.