G. Multiple and Divisor
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have $$$2n$$$ cards, and a positive integer $$$a_i$$$ is written on the $$$i$$$-th of them. Determine whether there exists a positive integer $$$x$$$ such that the cards can be split into two groups of $$$n$$$ cards each with the following properties:

  • every number in the first group divides $$$x$$$;
  • $$$x$$$ divides every number in the second group.

If so, find any such number.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$): the number of test cases. Then, $$$t$$$ test cases follow.

The first line of a test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

The second line contains $$$2n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{2n}$$$ ($$$1 \leq a_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print an integer: a suitable value of $$$x$$$. If there are several suitable values, print any of them. If no suitable value of $$$x$$$ exists, print $$$-1$$$.

Example
Input
5
1
2 8
1
2 3
2
8 2 4 1
2
1 6 2 3
2
67 67 67 67
Output
4
-1
2
-1
67
Note

In the first test case of the sample, for example, $$$x = 2$$$, $$$x = 4$$$, and $$$x = 8$$$ work.

In the second test case, there is no suitable value of $$$x$$$.