D. Introduction to Number Theory
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver has just learned about divisors and multiples in elementary school. Now, Busy Beaver challenges you with the following problem.

You are given a sequence $$$a$$$ of length $$$N$$$. Find any positive integer $$$X$$$ such that:

  • For every $$$i$$$, $$$X$$$ is either a multiple or a divisor of $$$a_i$$$;
  • there exists at least one index $$$i$$$ such that $$$X$$$ is a multiple of $$$a_i$$$;
  • there exists at least one index $$$i$$$ such that $$$X$$$ is a divisor of $$$a_i$$$;

or determine that no such integer exists.

Input

The first line contains a single integer $$$T$$$ ($$$1\leq T\leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$N$$$ ($$$2\le N\le 3 \cdot 10^5$$$) — the length of the sequence $$$a$$$.

The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).

The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the value of $$$X$$$, or $$$-1$$$ if no such $$$X$$$ exists.

If there are multiple valid values for $$$X$$$, you may output any of them.

Scoring

There are two subtasks for this problem.

  • ($$$40$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$2000$$$.
  • ($$$60$$$ points): No additional constraints.
Example
Input
6
3
36 2 12
6
10 20 30 40 50 60
7
8 7 6 5 4 3 2
6
10 6 1 90 2 15
3
10 2 5
2
1 1
Output
6
10
-1
30
10
1
Note

In the first test case, $$$6$$$ is a divisor of $$$36$$$ and $$$12$$$, and is a multiple of $$$2$$$.

In the second test case, $$$10$$$ is a divisor of all elements, and also a multiple of $$$10$$$.

In the third test case, there is no integer that satisfies the constraints.