Read problem statements in [Mandarin], [Russian], and [Vietnamese] as well.

Chef is busy preparing for the next lunchtime, so he has given you the following task.

You are given an array a consisting of n positive integers. The goodness of the array a is defined as the GCD of all the elements in the array.
Formally, goodness $= GCD(a_{1}, a_{2}, \dots, a_{n})$.

You can perform the following type of operation:

Select any two elements of the array a_{i} and $a_{j} (i \ne j$ and 1 ≤ i, j ≤ n) and replace both a_{i} and a_{j} with $a_{i}\cdot a_{j}$.

You can perform this operation at most once. Find the maximum goodness of the array.

------ Input Format ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer n.
• The second line contains $n space-separated integers a_{1}, a_{2}, \dots, a_{n}$.

------ Output Format ------

For each test case, print a single line containing a single integer representing the maximum goodness of the array.

------ Constraints ------

$1 ≤ T ≤ 200$
$2 ≤ n ≤ 2\cdot10^{5}$
$1 ≤ a_{i} ≤ 10^{18}$
- The sum of $n$ over all test cases does not exceed $2\cdot10^{5}$
- It is guaranteed that the maximum goodness will not exceed $10^{18}$

------ subtasks ------

Subtask #1 (10 points):
$1 ≤ T ≤ 200$
$2 ≤ n ≤ 2000$
$1 ≤ a_{i} ≤ 10^{9}$
The sum of $n$ over all cases does not exceed $2000$

Subtask #2 (50 points):
$1 ≤ T ≤ 200$
$2 ≤ n ≤ 10^{5}$
$1 ≤ a_{i} ≤ 10^{9}$
The sum of $n$ over all cases does not exceed $10^{5}$

Subtask #3 (40 points): Original Constraints

----- Sample Input 1 ------
2
5
18 6 4 3 12
5
12 4 6 16 28
----- Sample Output 1 ------
6
4
----- explanation 1 ------
Test Case $1$: Choose $a_{3} = 4$ and $a_{4} = 3$. The new array is $[18, 6, 12, 12, 12]$ with GCD = $6$.

Test Case $2$: Choose $a_{1} = 12$ and $a_{3} = 6$. The new array is $[72, 4, 72, 16, 28]$ with GCD = $4$.

见题面

见题面