There are n hills in Konohagakure, the Hidden Village of the Land of Fire.

Naruto is standing on the peak of 1^st hill and wants to see the peak of the n^th hill. He can see the peak of hills ahead of him which have a height smaller than or equal to the one he is standing on, up to the next strictly taller hill. Naruto has the ability to jump from one hill to another. He can also use his chakra to cut a hill and reduce its height.

You are given two arrays A and H. Array H represents the height of hills.

The energy used in jumping from i^th hill to j^th hill is 2 times the absolute difference of A[i] and A[j]. If Naruto is standing on i^th hill, he can cut any hill from (i+1)^th to n^th which has a height greater than i^th hill. He can only reduce the height of a hill up to the height of i^th hill. The energy used in cutting j^th (i < j ≤ n) hill the absolute difference of H[i] and H[j].

You have to tell the minimum energy which will be used in order for Naruto to see the n^th hill.

Note : Naruto can’t jump on the n^th hill nor can he cut the n^th hill.

Constraints

1 ≤ t ≤ 20

2 ≤ n ≤ 10⁵

1 ≤ A[i] ≤ 100000

1 ≤ H[i] ≤ 100000

Input

1. The first line of the input contains a single integer t denoting the number of test cases. The description of t test cases follows.
2. The first line of each test case contains a single integer n denoting the number of hills.
3. The second line contains n space-separated integers A₁, A₂, A₃ ... A_n.
4. The third line contain n space-separated integers H₁, H₂, H₃ ... H_n representing the height of i^th hill.

Output

Your program should print one line of output for each test case.Output minimum energy which will be used in order for Naruto to see the n^th hill. If it is not possible for Naruto to see the peak of n^th hill then output -1.

Example

Input:
3
5
1 7 6 12 8
2 9 4 3 1
7
3 8 6 7 19 18 9
1 3 5 2 10 4 5
6
2 7 4 5 9 3
1 2 3 4 5 6

Output:
10
11
-1

Explanation:

Test case 1: Naruto can jump to 3^rd hill from where he can see the peak of 5^th hill. Energy= 2 * |1-6| = 10.

OR

Naruto can cut 2^nd, 3^rd, and 4^th hill without jumping anywhere. Energy = |2-9| + |2-4| + |2-3| = 10.

Test case 3: Naruto cannot see the peak of 6^th hill whatever he may do.