Chiaki has a sequence s₁, s₂, ..., s_n. She would like to change it to another sequence t₁, t₂, ..., t_n using the following operations:

• choose two indices l and r (l ≤ r), and add 1 to every nonzero element between the indices l and r (both inclusive).
• choose two indices l and r (l ≤ r), and subtract 1 from every nonzero element between the indices l and r (both inclusive).

Chiaki would like to know the minimum number of operations needed.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1 ≤ n ≤ 10⁵) — the length of the sequence.

The second line contains n integers s₁, s₂, ..., s_n (0 ≤ s_i ≤ 10⁹).

The third line contains n integers t₁, t₂, ..., t_n (0 ≤ t_i ≤ 10⁹).

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

Output

For each test case, output an integer denoting the minimum number of operations. If it is impossible to change the sequence, output -1 instead.

Sample Input

2
5
1 1 1 1 1
2 0 2 0 2
7
3 1 2 3 2 1 4
2 0 0 0 0 0 2

Sample Output

3
3

Hint

For the first test case:

.

The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple