C. Pair of GCD
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a$$$ containing $$$n$$$ elements.

Find the maximum value of $$$^\dagger$$$ $$$gcd(a_1, a_2, a_3, \cdots , a_n)$$$, after applying the following operation exactly once :

  • Choose any $$$i,j(1 \le i \lt j \le n)$$$ and change $$$a_i$$$ and $$$a_j$$$ to any value.

$$$^\dagger$$$ $$$gcd(a_1, a_2, a_3, \cdots , a_n)$$$ denotes the greatest common divisor of $$$a_1, a_2, a_3, \cdots , a_n$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains single integer $$$n$$$ ($$$3 \le n \le 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ ($$$1 \le a_{i} \le 10^9$$$).

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

Output

For each test case, print single integer — the maximum value of $$$gcd(a_1, a_2, a_3, \cdots , a_n)$$$.

Example
Input
4
3
2 3 2
4
4 3 2 1
6
4 4 3 3 2 2
9
3 6 9 2 3 6 9 3 6
Output
3
2
2
3
Note

In the $$$1$$$-th test case, Choose $$$i = 1$$$ and $$$j = 3$$$ and change $$$a_i$$$ to $$$9$$$ and $$$a_j$$$ to $$$9$$$.

So the final array is $$$9, 3, 9$$$.

Hence, $$$gcd(9, 3, 9) = 3$$$.