Beautiful Partition

Peter has just learned what the greatest common divisor of a set of integers is. He likes the idea so much that now he looks for it in everything he sees.

During today's computer science lesson the teacher wrote an array of integers on the blackboard, and Peter noticed that its elements can be divided into two parts $M_1$ and $M_2$ so that $\gcd(M_1)$ and $\gcd(M_2)$ are both quite big. Here $\gcd(M)$ is the greatest common divisor of all numbers in $M$.

Peter has decided to generalize the problem. For a given array, divide all of its elements into two non-empty parts $M_1$ and $M_2$, with every element going into exactly one part, so that $\min(\gcd(M_1), \gcd(M_2))$ is as large as possible. Print that largest value.

The input contains several tests. The first line contains the number of tests $t$ ($1 \le t \le 1000$).

Each test is given on two lines. The first line contains an integer $n$ ($2 \le n \le 5 \times 10^4$), the size of the array. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$), the elements of the array.

The sum of the values of $n$ over all tests in one input does not exceed $5 \times 10^4$.

For each test print one integer on its own line: the largest possible value of $\min(\gcd(M_1), \gcd(M_2))$.