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 a1, a2, .... aN. He has somehow figured out that there exists some integer P such that the number X is divisible by P2, 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 a1, a2, .... aN.

-----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 1018 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 ≤ ai ≤ 1018

-----Subtasks-----
- Subtask 1[19 points]: 1 ≤ a1*a2*...*aN ≤ 106
- Subtask 2[22 points]: 1 ≤ a1*a2*...*aN ≤ 1012
- Subtask 3[23 points]: 1 ≤ ai ≤ 1012
- Subtask 4[36 points]: no additional constraints

-----Example-----
Input:
1
3
21 11 6

Output:
3

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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
import math
r = int(input())
for v in range(0, r):
	n = int(input())
	x = 1
	arr = list(map(int, input().strip().split(' ')))
	for i in range(0, n):
		x = x * arr[i]
	for i in range(2, 100000000):
		if x % pow(i, 2) == 0:
			ans1 = i
			break
	print(ans1)


import math

def forloop(list, list1):
	r = 1
	for x in list:
		r *= x
		for i in list1:
			if r % i == 0:
				break
	return i
t = int(input())
while t > 0:
	l1 = []
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(2, 1000000):
		l1.append(i * i)
	l1 = tuple(l1)
	n1 = forloop(l, l1)
	ans = math.sqrt(n1)
	print(int(ans))
	t -= 1


import math
for i in range(int(input())):
	y = int(input())
	x = list(map(int, input().split()))
	p = 1
	for j in x:
		p = p * j
	m = max(x)
	r = 1
	for k in range(2, m):
		if p % k ** 2 == 0:
			r = k
			break
	print(r)


import fractions

def repeat_factor(n):
	fs = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			q = n / i
			if q % i == 0:
				return i
	return 1
nprobs = int(input())
for i in range(nprobs):
	x = input()
	prob = list(map(int, input().split()))
	found = False
	prod = 1
	for i in prob:
		prod *= i
	x = repeat_factor(prod)
	print(x)


from collections import *

def prime(n):
	d = 2
	while d * d <= n:
		while n % d == 0:
			primef.append(d)
			n = n // d
		d += 1
	if n > 1:
		primef.append(n)
for _ in range(eval(input())):
	primef = []
	(x, prod) = (eval(input()), 1)
	m = list(map(int, input().split()))
	for i in m:
		prime(i)
	for i in primef:
		if primef.count(i) >= 2:
			break
	print(i)


import math

def gen_primes(num):
	nonlocal primes
	flag = False
	j = 0
	for i in range(primes[-1] + 1, num + 1):
		while primes[j] < math.sqrt(i):
			if i % primes[j] == 0:
				flag = True
				break
			j += 1
		if flag:
			flag = False
			pass
		else:
			primes.append(i)

def divisible(num):
	nonlocal primes, d, divisors
	srt = int(round(math.sqrt(num)))
	if srt <= primes[-1]:
		for i in primes:
			if num % (i * i) == 0:
				d = i
				return True
			elif num % i == 0:
				if divisors.get(i, 0):
					d = i
					return True
				else:
					divisors[i] = 1
	else:
		gen_primes(srt)
		for i in primes:
			if num % (i * i) == 0:
				d = i
				return True
			elif num % i == 0:
				if divisors.get(i, 0):
					d = i
					return True
				else:
					divisors[i] = 1
primes = [2, 3, 5, 7, 11]
for i in range(eval(input())):
	n = eval(input())
	l = input().strip().split()
	divisors = {}
	d = 0
	for j in range(n):
		l[j] = int(l[j])
		check = divisible(l[j])
		if check:
			print(d)
			break


import math

def divisorGenerator(n):
	large_divisors = []
	for i in range(2, int(math.sqrt(n) + 1)):
		if n % i == 0:
			yield i
			if i * i != n:
				large_divisors.append(n / i)
	for divisor in reversed(large_divisors):
		yield divisor
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	p = 1
	for i in a:
		p = p * i
	s = list(divisorGenerator(p))
	for j in s:
		if p % j ** 2 == 0:
			print(j)
			break
	t = t - 1