We guessed some integer number $x$. You are given a list of almost all its divisors. Almost all means that there are all divisors except $1$ and $x$ in the list.

Your task is to find the minimum possible integer $x$ that can be the guessed number, or say that the input data is contradictory and it is impossible to find such number.

You have to answer $t$ independent queries.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 25$) — the number of queries. Then $t$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 300$) — the number of divisors in the list.

The second line of the query contains $n$ integers $d_1, d_2, \dots, d_n$ ($2 \le d_i \le 10^6$), where $d_i$ is the $i$-th divisor of the guessed number. It is guaranteed that all values $d_i$ are distinct.


-----Output-----

For each query print the answer to it.

If the input data in the query is contradictory and it is impossible to find such number $x$ that the given list of divisors is the list of almost all its divisors, print -1. Otherwise print the minimum possible $x$.


-----Example-----
Input
2
8
8 2 12 6 4 24 16 3
1
2

Output
48
4

Difficulty: introductory

Starter code:

Solutions:
for q in range(int(input())):
    n = int(input())
    D = list(map(int, input().split()))
    D.sort()
    z = D[0] * D[-1]
    if z == -1:
        print(-1)
    else:
        Dz = set()
        for i in range(2, int(z ** 0.5) + 1):
            if z % i == 0:
                Dz.add(i)
                Dz.add(z // i)
        if Dz == set(D):
            print(z)
        else:
            print(-1)

from functools import reduce
import operator

t = int(input())
for _ in range(t):
    n = int(input())
    ds = sorted(map(int, input().split()))
    suspect = ds[0] * ds[-1]
    pfs = []
    g = suspect
    for i in range(2, int(g**0.5) + 1):
        if g % i == 0:
            pfs.append([0, i])
            while g % i == 0:
                pfs[-1][0] += 1
                g //= i
    if 1 < g: pfs.append([1, g])
    nf = reduce(operator.mul, [u[0] + 1 for u in pfs])
    ok = nf == len(ds) + 2
    for d in ds:
        if suspect % d != 0:
            ok = False
    if ok: print(suspect)
    else: print(-1)


for _ in range(int(input())):
    n=int(input())
    a=sorted(list(map(int,input().split())))
    ans=a[0]*a[-1]
    b=set(a)
    r=[]
    for i in range(2,int(ans**.5+1)):
        if ans%i==0:
            r.append(i)
            r.append(ans//i)
    if set(r)!=b:
        print(-1)
    else:
        print(ans)


t = int(input())
for _ in range(t):
    n = int(input())
    d = list(map(int, input().split()))
    d.sort()
    ans = d[0]*d[-1]
    flag = 1
    for i in range((n+1)//2):
        if d[i]*d[-1-i] != ans:
            flag = 0
            break
    if flag == 1:
        count = 0
        for i in range(1, int(ans**(1/2))+1):
            if ans % i == 0:
                if i**2 == ans:
                    count += 1
                else:
                    count += 2
        if count-2 == n:
            print(ans)
        else:
            print(-1)
    else:
        print(-1)


import math
for test in range(int(input())):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    x, flag = a[0] * a[-1], 0
    for i in range(len(a)):
        if a[i] * a[-1 - i] != x:
            flag = 1
            break
    if flag == 1:
        print(-1)
        continue
    b = []
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            b.append(i)
            if i != x // i:
                b.append(x // i)
    b = sorted(b)
    if len(a) != len(b):
        print(-1)
        continue
    flag = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            flag = 1
            break
    if flag:
        print(-1)
    else:
        print(x)

def divisors(n):
    res = set()

    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            res.add(i)
            res.add(n//i)
    
    return res

def solve():
    for _ in range(int(input())):
        N = int(input())
        D = set([int(k) for k in input().split()])
        
        ans = max(D) * min(D)
        
        if divisors(ans) != D:
            print(-1)
            continue
            
        print (ans)
    
def __starting_point():  
    solve() 

__starting_point()

def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    def prime_sieve(n):
        """returns a sieve of primes >= 5 and < n"""
        flag = n % 6 == 2
        sieve = bytearray((n // 3 + flag >> 3) + 1)
        for i in range(1, int(n ** 0.5) // 3 + 1):
            if not (sieve[i >> 3] >> (i & 7)) & 1:
                k = (3 * i + 1) | 1
                for j in range(k * k // 3, n // 3 + flag, 2 * k):
                    sieve[j >> 3] |= 1 << (j & 7)
                for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
                    sieve[j >> 3] |= 1 << (j & 7)
        return sieve

    def prime_list(n):
        """returns a list of primes <= n"""
        res = []
        if n > 1:
            res.append(2)
        if n > 2:
            res.append(3)
        if n > 4:
            sieve = prime_sieve(n + 1)
            res.extend(
                3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not (sieve[i >> 3] >> (i & 7)) & 1)
        return res

    primes = prime_list(10**6)

    t = read_int()
    for _ in range(t):
        n = read_int()
        divisors = sorted(read_int_array())
        x = divisors[0] * divisors[-1]
        should_have = 1
        x2 = x
        for p in primes:
            if p > x2:
                break
            if x2 % p == 0:
                options = 1
                while x2 % p == 0:
                    options += 1
                    x2 //= p
                should_have *= options

        if should_have != n + 2:
            write(-1)
            continue

        l, r = 0, len(divisors) - 1
        while l <= r:
            if divisors[l] * divisors[r] != x:
                write(-1)
                break
            l += 1
            r -= 1
        else:
            write(x)

main()


from functools import reduce
def factors(n):
	from functools import reduce
	return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

for _ in range(int(input().strip())):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	num = max(arr)*min(arr)
	s1 = set(arr)
	s1.add(1)
	s1.add(num)
	s2 = factors(num)
	if s1 == s2:
		print(num)
	else:
		print(-1)


t = int(input())
for q in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    ans = min(a)*max(a)
    deliver = [q for q in range(2, round(ans**(1/2))+1) if ans % q == 0]
    if deliver+[ans//deliver[q] for q in range(len(deliver)-1-(deliver[-1]**2 == ans), -1, -1)] == sorted(a):
        print(ans)
    else:
        print(-1)


for Valerchiclox in range(int(input())):
    n = int(input())
    c = list(map(int,input().split()))
    c.sort()
    const = c[0]*c[-1]
    k = -1
    for i in c:
        if i*c[k]!= const:
            const = -1
            break
        k-=1
    if const == -1:
        print(const)
    else:
        s = 0
        for i in range(2,int(const**0.5)+1):
            if const%i==0:
                s+=1
        if s*2-n%2==n:
            print(const)
        else:
            print(-1)

isPrime=[1 for i in range(1000005)]
primes=[]
for i in range(2,1000005):
    if(isPrime[i]==1):
        primes.append(i)
        j=2*i
        while(j<1000005):
            isPrime[j]=0
            j+=i

def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    return a*b/gcd(a,b)

t=int(input())
while(t>0):
    n=int(input())
    d=list(map(int,input().split()))
    d.sort()
    ans=1
    flag=1
    for i in range(len(d)-1):
        if(d[i]*d[n-i-1]!=d[i+1]*d[n-i-2]):
            flag=0
            break
    if(flag==0):
        print(-1)
    else:
        ans=d[0]*d[-1]
        amt=1
        x=ans
        for i in primes:
            if(ans%i==0):
                cnt=1
                while(x%i==0):
                    cnt+=1
                    x/=i
                amt*=cnt
        if(x>1):
            amt*=2
        if(amt-2==len(d)):
            print(int(ans))
        else:
            print(-1)
    """    
    for i in d:
        ans=lcm(ans,i)
        if(ans>10**30):
            print(-1)
            break
    if(ans>10**30):
        t-=1
        continue 
    if(ans==d[-1]):
        po=1
        flag=1
        for i in d:
            po*=d[0]
            if(po!=i):
                flag=0
        if(flag==1):
            print(int(ans*d[0]))
        else:
            print(-1)
    else:
        amt=1
        x=ans
        for i in primes:
            if(ans%i==0):
                cnt=1
                while(x%i==0):
                    cnt+=1
                    x/=i
                amt*=cnt
        if(x>1):
            amt*=2
        if(amt-2==len(d)):
            print(int(ans))
        else:
            print(-1)
    """
    t-=1


t=int(input())

def prov1(a):
    pp=a[0]*a[-1]
    for i in range(len(a)):
        if a[i]*a[-1-i]!=pp: return -1
    return pp

def kkk(a):
    i=2
    d=0
    while i*i<a:
       if a%i==0:
           d+=2
       i+=1
    if i*i==a: d+=1
    return d

def koka(a,b):
    ans=0
    while a%b==0:
        a=a//b
        ans+=1
    return ans



for i in range(t):
    n=int(input())
    a=sorted(list(map(int,input().split())))
    y=prov1(a)
    if y==-1:
        print(-1)
    else:
        yy=kkk(a[0])
        if yy>0: print(-1)
        else:
            u=kkk(a[-1])+2
            z=koka(a[-1],a[0])
            if z==0: d=u*2-2
            else:
                d=(u//(z+1))*(z+2)-2
            if d==n:
                print(y)
            else:
                print(-1)
            



t = int(input())
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
for i in range(t):
	n = int(input())
	l = list(map(int,input().split()))
	mini = min(l)
	maksi = max(l)
	a = mini * maksi
	c = 0
	for d in l:
		if a % d != 0:
			c = 1
			break
	
	if c == 1:
		print(-1)
		continue
	# ile divisors
	fac = []
	i = 2
	for p in prime:
		if p > max(maksi, mini):
			break
		if maksi % p != 0 and mini % p != 0:
			continue
		chuj = 0
		while True:
			if maksi % p == 0:
				maksi = maksi // p
				chuj += 1
			else:
				break
		while True:
			if mini % p == 0:
				mini = mini // p
				chuj += 1
			else:
				break	
		if chuj > 0:
			fac.append([p, chuj])
	czek = 1
	diwi = 1
	for f in fac:
		diwi = diwi * (f[1] + 1)
	if mini == maksi:
		if mini > 1:
			diwi *= 3
	else:
		if mini >1:
			diwi *= 2
		if maksi > 1:
			diwi *= 2
	if diwi - 2 == n:
		print(a)
	else:
		print(-1)


from collections import Counter
R = lambda: map(int, input().split())

def primefactors(n):
    f = 2
    while f * f <= n:
        while not n % f:
            yield f
            n //= f
        f += 1
    if n > 1:
        yield n

for _ in range(int(input())):
    n = int(input())
    dd = list(R())
    c = Counter()
    for d in dd:
        ct = Counter(primefactors(d))
        for k in ct: c[k] = max(c[k], ct[k])
    x = 1
    for k, v in c.items():
        x *= k**v
    if x==max(dd):
        t = min(dd)
        x *= t
        c[t] += 1
    m = 1
    for v in c.values(): m *= v+1
    print(x if m==len(dd)+2 else -1)

Q = int(input())

def decompose(x):
  ans = {}
  cx = x
  d = 2
  while d * d <= cx:
    t = 0
    while x % d == 0:
      t += 1
      x = x // d
    if t > 0:
      ans[d] = t
    d += 1
  if x > 1:
    ans[x] = 1
  return ans

def fastpow(x, p):
  if p == 0:
    return 1
  ans = fastpow(x, p // 2)
  ans *= ans
  if p % 2 == 1:
    ans *= x
  return ans

def makePrimePower(divs):
  primePowers = {}
  for d in divs:
    ppows = decompose(d)
    for key in ppows:
      if key not in primePowers:
        primePowers[key] = ppows[key]
      else:
        primePowers[key] = max(primePowers[key], ppows[key])
  return primePowers

def solve(divs):
  primePowers = makePrimePower(divs)
  x = 1
  for key in primePowers:
    x *= fastpow(key, primePowers[key])
  if x in divs:
    prim = list(primePowers.keys())[0]
    x *= prim
    primePowers[prim] += 1
  nrdivs = 1
  for key in primePowers:
    nrdivs *= primePowers[key] + 1
  if len(divs) + 2 != nrdivs:
    return -1
  return x

for x in range(Q):
  N = int(input())
  divs = list(map(int, input().split()))
  print(solve(divs))


import math
n=int(input())
result=[]
def divisors(n):
    count=0
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            if n//i==i:
                count+=1
            else:
                count+=2
    return count


for i in range(n):
    n1=int(input())
    n2=list((list(map(int,input().split()))))
    n2.sort()
    a1=n2[0]*n2[-1]
    final=True
    for i in range(len(n2)):
        if n2[i]*n2[len(n2)-1-i]!=a1:
            final=False
            break
    if n1==1 and n2[0]==1:
        result.append(1)
    elif final and n1==divisors(a1):
        result.append(a1)
    else:
        result.append(-1)
for i in result:
    print(i)



q = int(input())

def eratosthene(n):
    if n<2:
        return []
    n += 1
    tableau = [False,False] + [True]*(n-2)
    tableau[2::2] = [False]*((n-2)//2 + n%2) # sup. des nb pairs
    premiers = [2] # initialisation de la tableau des nb 1ers (2 est 1er)
    racine = int(n**0.5)
    racine = racine + [1,0][racine%2] # pour que racine soit impair
    for i in range(3, racine+1, 2):
        if tableau[i]:
            premiers.append(i)
            tableau[i::i] = [False]*((n-i)//i + int((n-i)%i>0)) 
    for i in range(racine, n, 2):
        if tableau[i]:
            premiers.append(i)
    return premiers

primes = eratosthene(10**6+2)

def divisors(n):

	ans = 1
	for p in primes:
		tmp = 0
		if n%p == 0:
			while True:
				tmp +=1
				n//=p
				if n%p != 0:
					break
		if tmp > 0:
			ans*=(tmp+1)
			tmp = 0
		if p > n:
			break
	return ans - 2

for _ in range(q):

	n = int(input())
	l = sorted(list(map(int, input().split())))

	if n == 1:
		if l[0] in primes:
			print(l[0]**2)
		else:
			print(-1)

	elif n > 1:
		candidate = l[0] * l[-1]
		for i in range(1, n // 2):
			if l[i]*l[n-1-i] != candidate:
				print(-1)
				break
		else:
			if divisors(candidate) == n:
				if n%2:
					if l[n//2]**2 == candidate:
						print(candidate)
					else:
						print(-1)
				else:
					print(candidate)
			else:
				print(-1)