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.

Difficulty: interview

Starter code:

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 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):
  arr[i]=arr[i]%1000000000000000007
 for i in range (0,n):
  x=x*arr[i]
  
 for i in range (2,1000000):
  if(x%(pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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):
  arr[i]=arr[i]%1000000007
 for i in range (0,n):
  x=x*arr[i]
  
 for i in range (2,1000000):
  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 l1:
   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
 # for i in range(len(prob)):
 #     for j in range(len(prob)):
 #         if (i != j):
 #             hcf = fractions.gcd(prob[i], prob[j])
 #             if hcf > 1:
 #                 print hcf
 #                 found = True
 #                 break
 #     if found:
 #         break
 # if found:
 #     break
 prod = 1
 for i in prob:
  prod *= i
 # for i in prob:
 #     x = repeat_factor(i)
 #     if x > 1:
 #         print x
 #         break
 x = repeat_factor(prod)
 print(x)



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):
  arr[i]=arr[i]%1000000007
 for i in range (0,n):
  x=x*arr[i]
  x%=1000000007
  
 for i in range (2,1000000):
  if(x%(pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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):
  arr[i]=arr[i]%1000000000000000007
 for i in range (0,n):
  x=x*arr[i]
  x%=1000000007
  
 for i in range (2,1000000):
  if(x%(pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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 forloop(list):
 r = 1
 for x in list:
  r *= x
 return r
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)
 for i in l1:
  if(n1%i==0):
   break;
 ans=math.sqrt(i)
 print(int(ans))
 t-=1

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]
  x%=1000000007
  
 for i in range (2,9000000):
  if(x%(pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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 


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,1000000):
  if(x%(pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


import math

for i in range(int(input())):
 y=int(input())
 x=list(map(int,input().split()))
 pr=1
 for j in x:
  pr=pr*j
 #s=min(x)
 m=max(x)
 #m=int(math.sqrt(m))
 #s=int(math.sqrt(s))
 rm=1
 #print s,m
 for k in range(2,m):
  #print k
  if pr%k**2==0:
   rm=k
   break
 print(rm) 
 


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,10000000):
  if(x%(pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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 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,20000000):
  if(x%(pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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,20000000):
  if(x%(math.pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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,80000000):
  if(x%(math.pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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,20000000):
  if(x%(math.pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1) 


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,15000000):
  if(x%(math.pow(i,2))==0):
   ans1=i
   break
 
 
 print(ans1)