Given two arrays $$$x$$$ and $$$y$$$ both of size $$$m$$$, let $$$z$$$ be another array of size $$$m$$$ such that the prefix maximum at each position of $$$z$$$ is the same as the prefix maximum at each position of $$$x$$$. Formally, $$$\operatorname{max}(x_1,x_2,\ldots,x_i)=\operatorname{max}(z_1,z_2,\ldots,z_i)$$$ should hold for all $$$1 \leq i \leq m$$$. Define $$$f(x,y)$$$ to be the maximum number of positions where $$$z_i=y_i$$$ over all possible arrays $$$z$$$.

You are given two sequences of integers $$$a$$$ and $$$b$$$, both of size $$$n$$$. Please find the value of $$$\sum_{l=1}^n\sum_{r=l}^n f([a_l,a_{l+1},\ldots,a_r], [b_l,b_{l+1},\ldots,b_r])$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \leq a_i \leq 2\cdot n)$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ $$$(1 \leq b_i \leq 2\cdot n)$$$.

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

Output

For each test case, output the sum of $$$f([a_l,a_{l+1},\ldots,a_r], [b_l,b_{l+1},\ldots,b_r])$$$ over all pairs of $$$(l,r)$$$.

Note

In the first test case, the answer is the sum of the following:

$$$f([5],[4])=0$$$, using $$$z=[5]$$$.
$$$f([3],[2])=0$$$, using $$$z=[3]$$$.
$$$f([1],[1])=1$$$, using $$$z=[1]$$$.
$$$f([5,3],[4,2])=1$$$, using $$$z=[5,2]$$$.
$$$f([3,1], [2,1])=1$$$, using $$$z=[3,1]$$$.
$$$f([5,3,1],[4,2,1])=2$$$, using $$$z=[5,2,1]$$$.

Prefix Maximum Invariance

Examples