Ja the Ghost is playing with rubber ducks. He has $$$n$$$ piles of rubber ducks arranged in a row, where the $$$i$$$-th pile contains $$$a_i$$$ ducks. Quack the Duck gives Ja a strictly increasing sequence $$$b_1,b_2,\ldots,b_n$$$ and commands him to make the piles $$$a_1,a_2,\ldots,a_n$$$ become exactly this sequence.

Ja performs the process in the following two stages:

Ja may add any number of ducks to each pile.
Formally, for each pile $$$i$$$, he chooses a non-negative integer $$$x_i$$$ and replaces $$$a_i$$$ with $$$a_i+x_i$$$.
Ja may repeatedly swap two adjacent piles.
Formally, he may perform the following operation any number of times, possibly zero: choose an index $$$i$$$ such that $$$1\le i\le n-1$$$, and swap the values of $$$a_i$$$ and $$$a_{i+1}$$$.

A process is called valid if, after both stages end, the sequence of pile sizes is exactly $$$b_1,b_2,\ldots,b_n$$$.

Find the minimum possible number of operations performed in the second stage among all valid processes. If there is no valid process, output $$$-1$$$.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 2000$$$) — the number of piles of rubber ducks.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — the initial number of rubber ducks in each pile.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_1 \lt b_2 \lt \cdots \lt b_n\le 10^9$$$) — the final number of rubber ducks in each pile.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, output a single integer — the minimum possible number of operations performed in the second stage among all valid processes. If there is no valid process, output $$$-1$$$.

Note

In the first test case, Ja only needs the first stage. He can set $$$x_1=0,x_2=1,x_3=3$$$, so the piles become $$$1,3,5$$$. No swaps are needed, so the answer is $$$0$$$.

In the second test case, Ja needs both stages. He can set $$$x_1=0,x_2=1,x_3=0$$$, so the piles become $$$2,3,1$$$. Then he can perform two swaps: $$$$$$ [2,3,1]\to [2,1,3]\to [1,2,3]. $$$$$$ The pile with $$$1$$$ duck must move from the third position to the first position, so at least two swaps are necessary. Therefore the answer is $$$2$$$.

In the third test case, it is impossible. The first pile initially contains $$$5$$$ ducks, but every number in the target sequence is at most $$$4$$$. Since Ja can only add ducks and cannot remove them, this pile cannot become equal to any number in the target sequence. Therefore the answer is $$$-1$$$.

In the fourth test case, no ducks need to be added. Ja only needs to reorder the piles into increasing order. The minimum number of adjacent swaps is $$$15$$$.

In the fifth test case, no ducks need to be added. Again, Ja only needs to reorder the piles into increasing order. The minimum number of adjacent swaps is $$$12$$$.

Annoying the Ghost

Examples