Zhongli gives you two arrays and of length . He asks you to divide into continuous subarrays(a division for index), each index belongs to exactly one subarray, and for these continuous subarrays you divided, each meets the condition .
Formally, you should find pairs satisfying following conditions:

• 
• for all
• for all
• for all

You should find the maximum .

输入描述:

The first line contains a single integer  --- the number of test cases.
The first line of each test case contains a single integer  --- the length of two arrays.
The second line of each test case contains  integers  --- the array .
The third line of each test case contains  integers  --- the array .
It is guaranteed that  over all test cases.

输出描述:

For each test case, output a single integer in a line --- the maximum , output  if there is no valid way to divide the two arrays.

2
5
1 2 3 4 5
2 2 2 2 2
3
1 2 2
2 2 2

3
-1