F. Legend Whispers
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the old city of Damascus, two ancient arrays, $$$a$$$ and $$$b$$$, each of length $$$n$$$, have been discovered by the greatest professor in his prime, George The Great

The legend whispers of a unique measure of beauty for these arrays:

  • If we cannot shuffle the array $$$a$$$ so that $$$a_i$$$ is divisible by $$$b_i$$$ for every $$$1 \le i \le n$$$, the beauty is messed up and becomes $$$-1$$$
  • However, If we can shuffle the array $$$a$$$ so that $$$a_i$$$ is divisible by $$$b_i$$$ for every $$$1 \le i \le n$$$, the beauty of the arrays will be equal to the $$$$$$\min_{1 \le i \le n} \{\frac{a_i}{b_i}\}$$$$$$

We ask you to print the maximal beauty you can get of the two arrays after rearrangement of the array $$$a$$$.

Input

The first line contains one integer number $$$(1 \le T \le 100)$$$ the number of test cases.

The first line of each test case contains an integer $$$(1 \le n \le 500)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,..,a_n (1 \le a_i \le 10^6)$$$. The third line contains $$$n$$$ integers $$$b_1,b_2,..,b_n (1 \le b_i \le 10^6)$$$.

An additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output

For each test case, print a single integer — The maximal beauty of $$$a$$$ and $$$b$$$, or $$$-1$$$ if there is no suitable arrangement.

Example
Input
2
3
6 10 12
1 2 3
3
1 2 3
3 3 3
Output
4
-1