You are given a grid $$$a$$$ of $$$2$$$ rows and $$$n$$$ columns, where every cell has value from $$$1$$$ to $$$2n$$$.

Let $$$f(l, r)$$$, where $$$1 \le l \le r \le 2n$$$, represent a binary$$$^{\text{∗}}$$$ grid $$$b$$$ of $$$2$$$ rows and $$$n$$$ columns, such that $$$b_{i, j} = 1$$$ if and only if $$$l \le a_{i, j} \le r$$$. Note that cell $$$(i, j)$$$ denotes the cell $$$i$$$ rows from the top and $$$j$$$ columns from the left.

Count the number of pairs of integers $$$(l, r)$$$ such that $$$1 \le l \le r \le 2n$$$, and in $$$f(l, r)$$$ there exists a down-right path of adjacent cells$$$^{\text{†}}$$$ with value of $$$1$$$ from cell $$$(1, 1)$$$ to $$$(2, n)$$$.

$$$^{\text{∗}}$$$A grid is considered binary if and only if every cell of it has value of $$$\mathtt{0}$$$ or $$$\mathtt{1}$$$.

$$$^{\text{†}}$$$A down-right path of adjacent cells is a sequence of cells such that each cell in the sequence shares either its top side or its left side with a side of the previous cell in the sequence.

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 a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of columns in the grid.

The second line contains exactly $$$n$$$ integers $$$a_{1, 1}$$$, $$$a_{1, 2}$$$, ..., $$$a_{1, n}$$$ ($$$1 \le a_{1, i} \le 2n$$$) — the values of the cells of the first row of the grid.

The third line contains exactly $$$n$$$ integers $$$a_{2, 1}$$$, $$$a_{2, 2}$$$, ..., $$$a_{2, n}$$$ ($$$1 \le a_{2, i} \le 2n$$$) — the values of the cells of the second row of the grid.

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

Output

For every test case, output on a separate line a single integer representing the number of pairs of integers $$$(l, r)$$$ such that $$$1 \le l \le r \le 2n$$$, and in $$$f(l, r)$$$ there exists a down-right path of adjacent cells with value of $$$1$$$ from cell $$$(1, 1)$$$ to $$$(2, n)$$$.

Note

Consider the first example.

The grids $$$f(1, 1), f(1, 2)$$$ will look like the following:

$$$$$$ \mathtt{10} $$$$$$ $$$$$$ \mathtt{01} $$$$$$

There does not exist a path of $$$1$$$s from the top-left cell to the bottom-right cell, therefore the pairs $$$(1, 1)$$$ and $$$(1, 2)$$$ are not counted.

The grids $$$f(1, 3)$$$ and $$$f(1, 4)$$$ will look like the following:

$$$$$$ \mathtt{11} $$$$$$ $$$$$$ \mathtt{11} $$$$$$

Since there exists a valid path from $$$(1, 1)$$$ to $$$(2, 2)$$$, the pairs $$$(1, 3)$$$ and $$$(1, 4)$$$ will be counted.

The grids $$$f(2, 2)$$$, $$$f(4, 4)$$$ will be the following:

$$$$$$ \mathtt{00} $$$$$$ $$$$$$ \mathtt{00} $$$$$$

The grids $$$f(2, 3)$$$, $$$f(2, 4)$$$, $$$f(3, 3)$$$, $$$f(3, 4)$$$ will look like the following:

$$$$$$ \mathtt{01} $$$$$$ $$$$$$ \mathtt{10} $$$$$$

So the pairs $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 3)$$$ and $$$(3, 4)$$$ will not be counted.

The only pairs counted where pairs $$$(1, 3)$$$ and $$$(1, 4)$$$, so the answer is $$$2$$$.

Monopati

Examples