You are given an array a consisting of n positive integers. You have to choose a positive integer d and paint all elements into two colors. All elements which are divisible by d will be painted red, and all other elements will be painted blue.

The coloring is called beautiful if there are no pairs of adjacent elements with the same color in the array. Your task is to find any value of d which yields a beautiful coloring, or report that it is impossible.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

The first line of each testcase contains one integer n (2 ≤ n ≤ 100) — the number of elements of the array.

The second line of each testcase contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^{18}).

Output

For each testcase print a single integer. If there is no such value of d that yields a beautiful coloring, print 0. Otherwise, print any suitable value of d (1 ≤ d ≤ 10^{18}).

Example

Input


5
5
1 2 3 4 5
3
10 5 15
3
100 10 200
10
9 8 2 6 6 2 8 6 5 4
2
1 3


Output


2
0
100
0
3
1
5
6 5 12 5 16
 1
5
3 5 6 11 2

2
 0

// package com.company

/*
 * @author :: Yuvraj Singh
 * CS UNDERGRAD AT IT GGV BILASPUR
 */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.max;
import static java.lang.System.out;

public final class Main {
    // Solution here

    void solve(){
        int n= in.nextInt();
        long[] arr= longArr(n);
        long evenGcd= arr[1], oddGcd= arr[0];
        for(int i=0;i<n;i+=2)
            oddGcd =gcd(oddGcd, arr[i]);
        for(int i=1;i<n;i+=2)
            evenGcd =gcd(evenGcd,arr[i]);

        boolean ok=true;
        for(int i=0;i<n;i+=2) {
            if(arr[i]%evenGcd==0) {
                ok=false;
                break;
            }
        }
        if(ok) {
            sb.append(evenGcd).append("\n");
            return;
        }
        ok=true;
        for(int i=1;i<n;i+=2) {
            if(arr[i]%oddGcd==0) {
                ok=false;
                break;
            }
        }
        if(ok) {
            sb.append(oddGcd).append("\n");
            return;
        }

        sb.append(0).append("\n");

    }




    // Starter Code
    FastReader in;
    StringBuffer sb;
    public static void main(String[] args) {
        new Main().run();
    }
    void run(){
        in= new FastReader();
        start();
    }
    void start(){
        sb= new StringBuffer();
        for(int t=in.nextInt();t>0;t--) {
            solve();
        }
        out.print(sb);
    }

    // Useful Functions
    void swap( int i , int j) {
        int tmp  = i;
        i = j;
        j = tmp;
    }
    long power(long x, long y, long p) {
        long res = 1;
        x = x % p;
        while (y > 0) {
            if (y % 2 == 1)
                res = (res * x) % p;

            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    int lower_bound(long[] a, long x) { // x is the target value or key
        int l=-1,r=a.length;
        while(l+1<r) {
            int m=(l+r)>>>1;
            if(a[m]>=x) r=m;
            else l=m;
        }
        return r;
    }
    int upper_bound(long[] arr, int key) {
        int i=0, j=arr.length-1;
        if (arr[j]<=key) return j+1;
        if(arr[i]>key) return i;
        while (i<j){
            int mid= (i+j)/2;
            if(arr[mid]<=key){
                i= mid+1;
            }else{
                j=mid;
            }
        }
        return i;
    }
    void sort(long[] A){
        int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            long tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
    }
    int[] intArr(int n){
        int[] res= new int[n];
        for(int i=0;i<n;i++){
            res[i]= in.nextInt();
        }
        return res;
    }
    long[] longArr(int n){
        long[] res= new long[n];
        for(int i=0;i<n;i++){
            res[i]= in.nextLong();
        }
        return res;
    }
    //    // sieve of eratosthenes code for precomputing whether numbers are prime or not up to MAX_VALUE
//    long MAX= MAX_VALUE;
//    int[] precomp= new int[(int) (MAX+1)];
//    void sieve(){
//        long n= MAX;
//        boolean[] prime = new boolean[(int) (n+1)];
//        for(int i=0;i<=n;i++)
//            prime[i] = true;
//
//        for(long p = 2; p*p <=n; p++)
//        {
//            // If prime[p] is not changed, then it is a prime
//            if(prime[(int) p])
//            {
//                // Update all multiples of p
//                for(long i = p*p; i <= n; i += p)
//                    prime[(int) i] = false;
//            }
//        }
//
//        // Print all prime numbers
//        for(long i = 2; i <= n; i++)
//        {
//            if(prime[(int) i])
//                precomp[(int) i]= 1;
//        }
//    }
    boolean isDigitSumPalindrome(long N) {
        // code here
        long sum= sumOfDigits(String.valueOf(N));
        long rev=0;
        long org= sum;
        while (sum!=0){
            long d= sum%10;
            rev = rev*10 +d;
            sum /= 10;
        }
        return org == rev;
    }
    long sumOfDigits(String n){
        long sum= 0;
        for (char c: n.toCharArray()){
            sum += Integer.parseInt(String.valueOf(c));
        }
        return sum;
    }
    long[] revArray(long[] arr) {
        int n= arr.length;
        int i=0, j=n-1;
        while (i<j){
            long temp= arr[i];
            arr[i]= arr[j];
            arr[j]= temp;
            i++;
            j--;
        }
        return arr;
    }
    long gcd(long a, long b){
        if (b==0)
            return a;
        return gcd(b, a%b);
    }
    long lcm(long a,long b){
        return (a*b)/gcd(a,b);
    }
    static class Pair implements Comparable<Pair>{
        long first;
        long second;
        Pair(long x, long y){
            this.first=x;
            this.second=y;
        }

        @Override
        public int compareTo(Pair o) {
            return 0;
        }
    }
    //    static class Compare {
//        static void compare(ArrayList<Pair> arr, int n) {
//            arr.sort(new Comparator<Pair>() {
//                @Override
//                public int compare(Pair p1, Pair p2) {
//                    return (int) (p2.first - p1.first);
//                }
//            });
//        }
//    }
    public static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            while (st==null || !st.hasMoreElements()){
                try{
                    st=new StringTokenizer(br.readLine());
                }catch (Exception e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        float nextFloat(){
            return Float.parseFloat(next());
        }
        String nextLine(){
            String str="";
            try{
                str=br.readLine();
            }catch (Exception e){
                e.printStackTrace();
            }
            return str;
        }
    }
}