Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
148 - The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - M
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:

.

Submit    Status