M. Sequence to Sequence
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Chiaki has a sequence s1, s2, ..., sn. She would like to change it to another sequence t1, t2, ..., tn 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 ≤ 105) – the length of the sequence.

The second line contains n integers s1, s2, ..., sn (0 ≤ si ≤ 109).

The third line contains n integers t1, t2, ..., tn (0 ≤ ti ≤ 109).

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

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.

Example
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
Output
3
3
Note

For the first test case: .