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.
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
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)