In a long tunnel, there are many moving ramps. For each ramp we know the distance L[i] (meters from the beginning of the tunnel), and its interval I[i]. Every ramp is first closed for I[i] seconds, and then it is opened for I[i] seconds, and so on. I[i] is the interval of the i-th ramp. You are in a car, at the start of the tunnel. The car you are driving has no brakes, and once you start, you are moving with constant speed of 1 meter per second, and you can't stop.

Your task is to calculate how many seconds you need to wait before you start, to pass the tunnel without hitting a single ramp. If there is no possible way to pass the tunnel without hitting a ramp, print '-1' (quotes for clarity).

Note: There can be multiple ramps on one spot.

Input

The first line of input contains one positive integer T (1 <= T <= 100), the number of test cases, followed by 3*T lines. Each 3 lines define a case. In the first line of each test case there is K (1 <= K <= 30), a single integer representing how many ramps there are. In the second line there are K integers separated with single space, where L[i] (1 <= L[i] <= 100) is the distance of the i-th ramp. In the third line there are K integers separated with single space, where I[i] (1 <= I[i] <= 20) is the interval of the i-th ramp.

Output

Print how many seconds you need to wait before you start, or -1 if there is no solution.

Constraints

Time limit: 5 seconds
Memory limit: 64 megabytes

Examples

input
3
3
1 2 3
3 3 3
3
1 2 3
2 2 2
11
18 1 39 35 17 28 2 23 6 34 14
2 13 13 5 10 19 11 8 19 13 9

output
3
-1
143481