Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 
Leha is a bright mathematician. Today he is investigating whether an integer is divisible by some square number or not.
He has a positive integer X represented as a product of N integers a_{1}, a_{2}, .... a_{N}. He has somehow figured out that there exists some integer P such that the number X is divisible by P^{2}, but he is not able to find such P himself. Can you find it for him? If there are more than one possible values of P possible, you can print any one of them.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. T test cases follow.
The first line of each test case contains one integer N denoting the number of intgers in presentation of X.
The second line contains N space-separated integers a_{1}, a_{2}, .... a_{N}.

------ Output ------ 

For each test case, output a single integer P deoting the answer for this test case. Note that P must be in range from 2 to 10^{18} inclusive. It's guaranteed that at least one answer exists. If there are more than one possible answers, print any.

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

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 100$
$1 ≤ a_{i} ≤ 10^{18}$

------ Subtasks ------ 

$Subtask 1[19 points]: 1 ≤ a_{1}*a_{2}*...*a_{N} ≤ 10^{6}$
$Subtask 2[22 points]: 1 ≤ a_{1}*a_{2}*...*a_{N} ≤ 10^{12}$
$Subtask 3[23 points]: 1 ≤ a_{i} ≤ 10^{12}$
$Subtask 4[36 points]: no additional constraints$

----- Sample Input 1 ------ 
1
3
21 11 6
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
Example case 1. X = 21 * 11 * 6 = 1386. It's divisible by 9 which is a square number, as 9 = 32. So P = 3.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
try:
	import math

	def computeGCD(x, y):
		while y:
			(x, y) = (y, x % y)
		return x

	def findsol(ai, n):
		for i in range(n - 1):
			for j in range(i + 1, n):
				if computeGCD(ai[i], ai[j]) > 1:
					return computeGCD(ai[i], ai[j])
		for i in range(n):
			x = ai[i]
			q = 1
			while q * q * q <= x:
				if q > 1 and x % (q * q) == 0:
					return q
				if x % q == 0:
					k = math.floor(math.sqrt(x // q))
					if k > 1 and k * k == x // q:
						return k
				q += 1
	for _ in range(int(input())):
		n = int(input())
		ai = list(map(int, input().split()))
		ans = findsol(ai, n)
		print(ans, end='\n')
except EOFError as e:
	print(end='')


import math

def solve(arr):
	for i in range(len(arr)):
		for j in range(i + 1, len(arr)):
			if math.gcd(arr[i], arr[j]) > 1:
				return math.gcd(arr[i], arr[j])
	for i in range(len(arr)):
		p = arr[i]
		j = 1
		while j * j * j <= p:
			if j > 1 and p % (j * j) == 0:
				return j
			if p % j == 0:
				k = math.floor(math.sqrt(p // j))
				if k > 1 and k * k == p // j:
					return k
			j += 1
	raise ValueError()
for _ in range(int(input())):
	n = int(input())
	arr = [int(c) for c in input().split()]
	print(solve(arr))


import math

def seive():
	m = 0
	M = 10 ** 6
	arr = [0] * (M + 1)
	arr[0] = arr[1] = 1
	for i in range(2, M + 1):
		if arr[i] == 0:
			j = i + i
			while j <= M:
				arr[j] = 1
				j += i
	pr = []
	for i in range(M + 1):
		if arr[i] == 0:
			pr += [i]
	return pr

def prog(prime):
	n = int(input())
	M = 10 ** 6
	num = [int(i) for i in input().split()]
	for i in range(n):
		for j in range(i + 1, n):
			x = math.gcd(num[i], num[j])
			if x != 1:
				print(x)
				return
	for x in num:
		i = x
		for j in prime:
			if i % j == 0:
				i /= j
				if i % j == 0:
					i /= j
					print(j)
					return
		if i >= M:
			sq = math.sqrt(i)
			sqi = int(sq)
			if sq == sqi:
				print(sqi)
				return
prime = seive()
for _ in range(int(input())):
	prog(prime)


from math import sqrt as S

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
from math import sqrt as S
for _ in range(int(input())):
	n = int(input())
	f = 0
	pf = {}
	l = [int(i) for i in input().split()]
	g = 0
	ans = 0
	for i in range(n):
		if ans:
			break
		for j in range(i + 1, n):
			g = gcd(l[i], l[j])
			if g > 1:
				ans = g
				break
	for i in range(n):
		if ans:
			break
		curr = l[i]
		pr = 1
		while pr * pr * pr <= curr:
			if curr % (pr * pr) == 0:
				if pr * pr > 1:
					ans = pr
			if curr % pr == 0:
				rem = curr // pr
				sq = S(rem)
				if sq == int(sq) and rem > 1:
					ans = int(sq)
			pr += 1
	print(ans)


def abcd():
	import random

	def gcd(a, b):
		if b % a == 0:
			return a
		elif a % b == 0:
			return b
		else:
			return gcd(min(a, b), max(a, b) % min(a, b))
	import sys
	from sys import stdin, stderr, stdout
	up = 1000000000
	K = int(up ** 0.5) + 1
	prime = []
	temp = [0] * (K + 1)
	temp[0] = 1
	temp[1] = 1
	for i in range(len(temp)):
		if temp[i] == 0:
			prime += [i]
			for j in range(2 * i, len(temp), i):
				temp[j] = 1

	def find(m, n):
		C = [0 for i in range(m, n + 1)]
		if m == 1:
			C[0] = 1
		K = int(n ** 0.5) + 1
		for x in prime:
			if x <= K:
				start = x ** 2
				if m > x ** 2:
					start = (m - x ** 2) // x * x + x ** 2
				for y in range(start, n + 1, x):
					if y >= m:
						C[y - m] = 1
			else:
				break
		ANS = []
		for i in range(len(C)):
			if C[i] == 0:
				ANS += [i + m]
		return ANS
	primes = find(2, 10 ** 6 + 1)

	def main():
		input()
		A = list(map(int, input().strip().split(' ')))
		random.shuffle(A)
		random.shuffle(A)
		for i in range(len(A)):
			for j in range(i + 1, len(A)):
				T = gcd(A[i], A[j])
				if T > 1:
					print(T)
					return 0
		for i in range(len(A)):
			tt = testing(A[i])
			if tt == 1:
				return 0

	def testing(B):
		for i in range(len(primes)):
			if B % primes[i] == 0:
				temp = primes[i]
				if B % temp ** 2 == 0:
					print(temp)
					return 1
				else:
					B = B // temp
		L = int(B ** 0.5)
		if L < 100:
			return 0
		if B % L ** 2 == 0:
			print(L)
			return 1
		elif B % (L + 1) ** 2 == 0:
			print(L + 1)
			return 1
		return 0
	for _ in range(int(input())):
		main()
abcd()