Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3970
Sequence to Sequence

Time Limit: 1 Second      Memory Limit: 65536 KB

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 (lr), and add 1 to every nonzero element between the indices l and r (both inclusive).
  • choose two indices l and r (lr), 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.

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:

.

Author: LIN, Xi
Source: The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status