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$.

Difficulty: VERY_HARD
Tags: Number theory

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
T = int(input())

def gcd(u, v):
	if v == 0:
		return u
	return gcd(v, u % v)
for t in range(T):
	N = int(input())
	A = [int(h) for h in input().split()]
	g = 0
	skip1 = []
	skip2 = []
	for a in A:
		for i in range(len(skip2)):
			(g2, skips) = skip2[i]
			skip2[i] = (gcd(g2, a), skips)
		for i in range(len(skip1)):
			(g1, skip) = skip1[i]
			skip2.append((g1, (skip, a)))
		skip2.sort(reverse=True)
		skip2_ = []
		for i in range(len(skip2)):
			admissible = True
			for j in range(i - 1, -1, -1):
				if skip2[j][0] % skip2[i][0] == 0:
					admissible = False
					break
			if admissible:
				skip2_.append(skip2[i])
		skip2 = skip2_
		for i in range(len(skip1)):
			(g1, skip) = skip1[i]
			skip1[i] = (gcd(g1, a), skip)
		skip1.append((g, a))
		skip1.sort(reverse=True)
		skip1_ = []
		for i in range(len(skip1)):
			admissible = True
			for j in range(i - 1, -1, -1):
				if skip1[j][0] % skip1[i][0] == 0:
					admissible = False
					break
			if admissible:
				skip1_.append(skip1[i])
		skip1 = skip1_
		g = gcd(g, a)
	if len(skip1) > 0:
		g = max(g, skip1[0][0])
	if len(skip2) > 0:
		g = max(g, gcd(skip2[0][0], skip2[0][1][0] * skip2[0][1][1]))
	print(g)