The Little Elephant from the Zoo of Lviv has an array A that consists of N positive integers. Let A[i] be the i-th number in this array (i = 1, 2, ..., N).

Find the minimal number x > 1 such that x is a divisor of all integers from array A. More formally, this x should satisfy the following relations:

A[1] mod x = 0, A[2] mod x = 0, ..., A[N] mod x = 0,

where mod stands for the modulo operation. For example,  8 mod 3 = 2,  2 mod 2 = 0, 100 mod 5 = 0 and so on. If such number does not exist, output -1.

-----Input-----

The first line of the input contains a single integer T, the number of test cases. T test cases follow. The first line of each test case contains a single integer N, the size of the array A for the corresponding test case. The second line contains N space separated integers A[1], A[2], ..., A[N].

-----Output-----

For each test case output a single line containing the answer for the corresponding test case.

-----Constraints-----
1 ≤ T ≤ 100000

1 ≤ N ≤ 100000

The sum of values of N in each test file does not exceed 100000

1 ≤ A[i] ≤ 100000

-----Example-----
Input:
2
3
2 4 8
3
4 7 5

Output:
2
-1

-----Explanation-----
Case 1. Clearly 2 is a divisor of each of the numbers 2, 4 and 8. Since 2 is the least number greater than 1 then it is the answer.

Case 2. Let's perform check for several first values of x.

x4 mod x7 mod x5 mod x20113112403154206415740584759475

As we see each number up to 9 does not divide all of the numbers in the array. Clearly all larger numbers also will fail to do this. So there is no such number x > 1 and the answer is -1.

Difficulty: interview

Starter code:

Solutions:
from math import sqrt,gcd

for _ in range(int(input())):
    n=int(input())
    ar=[int(x) for x in input().split()]
    g=ar[0]
    for i in range(1,n):
        g=gcd(g,ar[i])
    
    f=g
    for i in range(2,int(sqrt(g))+1):
        if g%i==0:
            f=i
            break
    if g!=1:
        print(f)
    else:
        print(-1)
        
        
    

from math import gcd,sqrt

T = int(input())
ans = []

for _ in range(T):
    N = int(input())
    A = [int(i) for i in input().split()]

    g = A[0]
    for i in range(1,N):
        g = gcd(g,A[i])

    f = g
    # print(g,'$')
    for i in range(2,int(sqrt(g))+1):
        if(g%i==0):
            f = i
            break
    if(g!=1):
        ans.append(f)
    else:
        ans.append(-1)

for i in ans:
    print(i)

# cook your dish here
import math

for _ in range(int(input())):
    n=int(input())
    l=list(map(int, input().split()))
    if l[0]==1:
        print(-1)
        
    else:
        l1=[l[0]]
        flag=0
        for i in range(1, n):
            p=math.gcd(l1[-1], l[i])
            if p==1:
                print(-1)
                flag=1 
                break
            
            else:
                l1.append(p)

        if flag==0:
            p=l1[-1]
            for i in range(2, int(p**0.5)+1):
                if p%i==0:
                    print(i)
                    flag=1 
                    break
                
        if flag==0:
            print(p)

from functools import reduce
from math import gcd
def sieve(n):
    start = int(n**0.5) +2
    arr =[True]*(n+1)
    primes= []
    for i in range(2,start):
        if arr[i]==True:
            primes.append(i)
        for j in range(i*2,n+1,i):
            arr[j]=False
    #saved till start primes now saving from start till n
    for i in range(start,n+1):
        if arr[i] ==True:
            primes.append(i)
    return primes
def divs(n,primes):
    sq= n**0.5
    fac =[]
    for i in primes:
        if i > sq:
            break
        if n%i==0:
            fac.append(i)
    if len(fac)==0:
        fac = [n]
    return fac
primes =sieve(int((10**5)**0.5+1))
#print(primes)
for _ in range(int(input())):
    n = int(input())
    ls = [int(X)  for X in input().split()]
    gc = reduce(gcd,ls)
    x = divs(gc,primes)
    if x[0]!=1:
        print(x[0])
    elif x[0]==1 and len(x)>1:
        print(x[1])
    else:print(-1)











    #gcd gives you the greatest common divisor simply printing this is incorrect
    #since gcd divides all the numbers in the array it's divisors will also do the same
    #find the smallest divisor (smallest prime)

from functools import reduce
from math import gcd
def sieve(n):
    start = int(n**0.5) +2
    arr =[True]*(n+1)
    primes= []
    for i in range(2,start):
        if arr[i]==True:
            primes.append(i)
        for j in range(i*2,n+1,i):
            arr[j]=False
    #saved till start primes now saving from start till n
    for i in range(start,n+1):
        if arr[i] ==True:
            primes.append(i)
    return primes
def divs(n,primes):
    sq= n**0.5
    fac =[]
    for i in primes:
        if i > sq:
            break
        if n%i==0:
            fac.append(i)
    if len(fac)==0:
        fac = [n]
    return fac
primes =sieve(int((10**5)**0.5+1))
#print(primes)
for _ in range(int(input())):
    n = int(input())
    ls = [int(X)  for X in input().split()]
    gc = reduce(gcd,ls)
    x = divs(gc,primes)
    if x[0]!=1:
        print(x[0])
    elif x[0]==1 and len(x)>1:
        print(x[1])
    else:print(-1)











    #gcd gives you the greatest common divisor simply printing this is incorrect
    #since gcd divides all the numbers in the array it's divisors will also do the same
    #find the smallest divisor (smallest prime)

from functools import reduce
from math import gcd
def divisor(n):
    i = 3
    while i*i <= n:
        if n%i==0:
            return i
        i+=2
    return n
for _ in range(int(input())):
    n = int(input())
    ls = [int(X)  for X in input().split()]
    gc = reduce(gcd,ls)
    #gcd gives you the greatest common divisor simply printing this is incorrect
    #since gcd divides all the numbers in the array it's divisors will also do the same
    #find the smallest divisor (smallest prime)
    if gc ==1:
        print(-1)
    elif gc %2 ==0:
        print(2)
    else:
        print(divisor(gc))

# cook your dish here
import math
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    s=l[0]
    for i in range(1,n):
        s=math.gcd(s,l[i])
    if s==1:
        print(-1)
    elif s%2==0:
        print(2)
    else:
        ans=0
        for i in range(3,int(s**0.5)+1):
            if s%i==0:
                ans=i 
                break 
        if ans==0:
            print(s)
        else:
            print(ans)
    

import math
T = int(input())
while T:
    N = int(input())
    A = list(map(int, input().split()))
    hcf = A[0]
    n = len(A)
    for i in range(1,len(A)):
        hcf = math.gcd(hcf, A[i])
    if hcf == 1:
        print(-1)
    elif hcf % 2 == 0:
        print(2)
    else:
        answer = 0
        for j in range(3, int(hcf ** 0.5)+1):
            if hcf%j == 0:
                answer = j
                break
        if answer == 0:
            print(hcf)
        else:
            print(answer)
    T -= 1

# cook your dish here
from math import gcd
for _ in range(int(input())):
    
    n = int(input())
    l = list(map(int,input().split()))
    
    g=l[0]
    
    for x in l:
        g = gcd(x,g)
        
    if g==1:
        print(-1)
    elif g%2==0:
        print(2)
    else:
        
        for i in range(3,int((g)**0.5) +1):
           
            if g%i==0:
                
                print(i)
                break
        else:
            print(g)
                


import math
test = int(input())
for _ in range(test):
    n = int(input())
    array = list(map(int, input().split()))
    hcf = array[0]
    for i in range(1, n):
        hcf = math.gcd(hcf, array[i])
    
    if hcf==1:
        print(-1)
    elif hcf%2==0:
        print(2)
    else:
        answer=0
        for i in range(3, int((hcf)**0.5) +1):
            if hcf%i==0:
                answer = i
                break
        if answer==0:
            print(hcf)
        else:
            print(answer)

import math
def hcf(a,b):
    if a==0:
        return 1
    if a%b==0:
        return b
    return hcf(b,a%b)
        
t=int(input())
for _ in range(t):
    n=int(input())
    list1=list(map(int,input().strip().split()))
    
    curr=list1[0]
    for i in range(1,n):
        curr=hcf(curr,list1[i])
        if curr==1:
            break

    if curr==1:
        print(-1)
    else:
        ans=-1
        for i in range(2,math.floor(math.sqrt(curr))+1):
            if curr%i==0:
                ans=i
                break
        
        if ans==-1:
            #curr is a prime number
            print(curr)
        else:
            print(i)
        
        
            
       
    
    
    
    


import math
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    x = a[0]
    for i in a:
        x = math.gcd(i, x)
    if x == 1:
        k = -1
    else:
        k = x
        x1 = x ** 0.5
        t = int(x1)
        for i in range(2, t + 1):
            if x % i == 0:
                k = i
                break
    print(k)


def __starting_point():
    t = int(input())
    while t != 0:
        solve()
        t -= 1
__starting_point()

import functools
import math
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    g_1=functools.reduce(math.gcd,l)
    if g_1==1:
        print(-1)
        continue
    t_1=int(math.sqrt(g_1))
    c=0
    for i in range(2,t_1+2):
        if g_1%i==0:
            c=i
            break
    if c==0:
        print(g_1)
    else:
        print(c)

# cook your dish here
import math
for _ in range(int(input())):
    n=int(input())
    a=map(int,input().split())
    a=list(a)
    x=a[0]
    for i in a:
        x=math.gcd(i,x)
    if x==1:
        k=-1
    else:
        k=x
        x1=x**0.5
        t=int(x1)
        for i in range(2,t+1):
            if(x%i==0):
                k=i
                break
    print(k)

import math
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    g = a[0]
    for i in a:
        g = math.gcd(g,i)
    if g == 1:
        print(-1)
    else:
        for i in range(2,int(math.sqrt(g)) + 1):
            if g%i == 0:
                print(i)
                break
        else:
            print(g)


from functools import reduce
from math import sqrt
from math import gcd
for i in range(int(input())):
	n = int(input())
	li= list((int(i) for i in input().split()))
	a  = reduce(lambda a,b:gcd(a,b),li)
	if a==1:
		print(-1)
	else:
		for i in range(2,int(sqrt(a))+1):
			if a%i==0:
				print(i)
				break
		else:
			print(a)

from math import *
for j in range(int(input())):
    n=int(input())
    x=list(map(int,input().split()))
    a=x[0]
    am=0
    for i in range(1,n):
        a=gcd(a,x[i])
    if(a==1):
        print(-1)
    else:
        for i in range(2,int(sqrt(a))+1):
            if(a%i==0):
                print(i)
                am=1
                break
        if(am==0):
            print(a)

# cook your dish here
import math
test=int(input())
for _ in range(test):
    n=int(input())
    l=list(map(int,input().split()))
    for i in range(1, n):
        l[i]=math.gcd(l[i],l[i-1])
    a=l[-1]
    if a==1:
        print(-1)
    else:
        f=0
        p=int(math.sqrt(l[-1]))
        i=2
        while i<=p:
            if a%i==0:
                print(i)
                f=1
                break
            i+=1
        if f==0:
            print(a)

import math
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    for i in range(1, n):
        l[i]=math.gcd(l[i],l[i-1])
    a=l[-1]
    if a==1:
        print(-1)
    else:
        f=0
        p=int(math.sqrt(l[-1]))
        i=2
        while i<=p:
            if a%i==0:
                print(i)
                f=1
                break
            i+=1
        if f==0:
            print(a)

# cook your dish here
# cook your dish here
from math import gcd,sqrt
for _ in range(int(input())):
        s=0
        f=1
        n=int(input())
        a=list(map(int,input().split()))
        for i in range(len(a)):
                s=gcd(s,a[i])
        if(s==1):
                print(-1)
        else:
            for i in range(2,int(sqrt(s))+1):
                        if(s%i==0):
                                print(i)
                                f=0
                                break;
            if(f==1):
                        
                        print(s)        
                        

           
                         

                        
           

# cook your dish here
from math import gcd,sqrt
for _ in range(int(input())):
        s=0
        f=1
        n=int(input())
        a=list(map(int,input().split()))
        for i in range(len(a)):
                s=gcd(s,a[i])
        if(s==1):
                print(-1)
        else:
                for i in range(2,int(sqrt(s))+1):
                        if(s%i==0):
                                print(i)
                                f=0
                                break;
                if(f==1):
                        
                        print(s)