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

import java.lang.reflect.Array;
import java.util.*;
import java.io.*;

//import static com.sun.tools.javac.jvm.ByteCodes.swap;




public class fastTemp {

     static class Pair {
         int wall;
         int pos;

         Pair(int wall, int pos) {
             this.wall = wall;
             this.pos = pos;
         }
     }

     static FastScanner ps = null;


     public static void main(String[] args) {
         ps = new FastScanner();
         PrintWriter out = new PrintWriter(System.out);
        int t = ps.nextInt();
        while(t-->0) {
            int n = ps.nextInt();
            int ar[] = {2,4,3,9,5,25,7,49,11,121};
            long arr[] = new long[n];
            for(int i=0;i<n;i++){
                arr[i] = ps.nextLong();
            }
            boolean f = false;
            long ans = 0;

            for(int i=0;i<ar.length;i++){
                long y = ar[i];
                int x = 1;
                if(arr[0]%y==0){
                    x = 1;
                }else{
                    x = 0;
                }
                for(int j=0;j<n;j++){
                    if(arr[j]%y==0 && x==1){
                        x = 0;
                    }else if(arr[j]%y!=0 && x==0){
                        x=1;
                    }
                    else if((arr[j]%y==0 && x==0) || (arr[j]%y!=0 && x==1)){
                        f = true;
                        break;
                    }
                }
                if(f){
                    f = false;
                    continue;
                }else{
                    ans = y;
                    break;
                }

            }

            if(!f){
                out.println(ans);
            }else{
                out.println(0);
            }


        }
        out.close();
 }
 public static boolean find(int x,int id,int[] arr){
         for(int i=id;i>=1;i--){
             if(arr[i] == x){
                 return true;
             }
         }
         return false;
 }
    public static void solve(int[] ar,int s , int e,int i){


          int ls = upper_bound(ar,i,s);
          int le = upper_bound(ar,i,e);

       int ids = (ls+1) - (ar[ls] - s);
       int ide  = (le+1)- ( ar[le] - e);

       long ld = le-ls;
       long cd = ide - ids;
     if(ld<0 || ld<cd || cd<0){
      System.out.println(0);
      }else{

         if(cd == 0){
             System.out.println(1);
          }else{
              long ans = 1;
              ans  =nCrModPFermat(ld,cd,1000000007);

              int x = 1;
              System.out.println(ans);
         }


      }



          }
     static long power(long x, long y, long p)
     {

         // Initialize result
         long res = 1;

         // Update x if it is more than or
         // equal to p
         x = x % p;

         while (y > 0) {

             // If y is odd, multiply x
             // with result
             if (y % 2 == 1)
                 res = (res * x) % p;

             // y must be even now
             y = y >> 1; // y = y/2
             x = (x * x) % p;
         }

         return res;
     }

     // Returns n^(-1) mod p
     static long modInverse(long n, long p)
     {
         return power(n, p - 2, p);
     }

     // Returns nCr % p using Fermat's
     // little theorem.

     static long nCrModPFermat(long n, long r, long p)
     {

         if (n<r)
             return 0;
         // Base case
         if (r == 0)
             return 1;

         // Fill factorial array so that we
         // can find all factorial of r, n
         // and n-r
         long[] fac = new long[(int)n + 1];
         fac[0] = 1;

         for (int i = 1; i <= n; i++)
             fac[i] = fac[i - 1] * i % p;

         return (fac[(int)n] * modInverse(fac[(int)r], p) % p * modInverse(fac[(int)n - (int)r], p) % p) % p;
     }


//public static int dijkstra(int src , int dist[] ){
//
//PriorityQueue<Pair> q = new PriorityQueue<>();
//q.add(new Pair(1,0));
//
//while(q.size()>0){
//
//    Pair rem = q.remove();
//    for(Pair x:graph[rem.y]){
//        if(dist[x.y]>dist[rem.y]+x.wt){
//            dist[x.y] = dist[rem.y] + x.wt;
//            q.add(new Pair(x.y,dist[x.y]));
//        }
//    }
//
//}
//
//return dist[dist.length-1];
//
//}
 // T --> O(n) && S--> O(d)




  static int upper_bound(int arr[], int N, int X)
     {
         int mid;

         // Initialise starting index and
         // ending index
         int low = 0;
         int high = N;

         // Till low is less than high
         while (low < high) {
             // Find the middle index
             mid = low + (high - low) / 2;

             // If X is greater than or equal
             // to arr[mid] then find
             // in right subarray
             if (X > arr[mid]) {
                 low = mid + 1;
             }

             // If X is less than arr[mid]
             // then find in left subarray
             else if(X<arr[mid]){

                 high = mid;
             }
             else{
                 return mid;
             }
         }

         // if X is greater than arr[n-1]
         if(low < N && arr[low] <= X) {
             low++;
         }

         // Return the upper_bound index
         return low;
     }





    public static class String1 implements Comparable<String1>{
        String str;
        int id;
        String1(String str , int id){
            this.str = str;
            this.id = id;
        }
        public  int compareTo(String1 o){
            int i=0;
            while(i<str.length() && str.charAt(i)==o.str.charAt(i)){
                i++;
            }
            if(i<str.length()){
                if(i%2==1){
                    return o.str.compareTo(str);   // descending order
                }else{
                    return str.compareTo(o.str);  // ascending order
                }
            }
            return str.compareTo(o.str);
        }
    }


    static void sort(int[] a) {
        ArrayList<Integer> l=new ArrayList<>();
        for (int i:a) l.add(i);
        Collections.sort(l);
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }
    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
    // ------------------------------------------swap----------------------------------------------------------------------

    static void swap(int arr[],int i,int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }


    //-------------------------------------------seiveOfEratosthenes----------------------------------------------------


    static boolean prime[];
    static void sieveOfEratosthenes(int n)
    {
        // Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.
        prime= new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++)
        {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == true)
            {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }

        // Print all prime numbers
//        for (int i = 2; i <= n; i++)
//        {
//            if (prime[i] == true)
//                System.out.print(i + " ");
//        }
    }



    //------------------------------------------- power------------------------------------------------------------------



    public static long power(int a , int b) {
        if (b == 0) {
            return 1;
        } else if (b == 1) {
            return a;

        } else {

            long R = power(a, b / 2);
            if (b % 2 != 0) {


                return (((power(a, b / 2))) * a * ((power(a, b / 2))));
            } else {
                return ((power(a, b / 2))) * ((power(a, b / 2)));
            }
        }

    }



    //--------------------------------------lower bound----------------------------------------------------------


    static int LowerBound(int a[], int 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;
    }

    //--------------------------------------------------------------------------------------------------------------
    public static int log2(int x) {
        return (int) (Math.log(x) / Math.log(2));
    }

    //---------------------------------------EXTENDED EUCLID ALGO--------------------------------------------------------
  /*  public static class Pair{
        int x;
        int y;
        public Pair(int x,int y){
            this.x = x;
            this.y = y ;
        }
    }
*/
//    public static Pair Euclid(int a,int b){
//
//        if(b==0){
//            return new Pair(1,0);  // answer of x and y
//        }
//
//        Pair dash = Euclid(b,a%b);
//
//        return new Pair(dash.y , dash.x - (a/b)*dash.y);
//
//
//    }
//--------------------------------GCD------------------GCD-----------GCD--------------------------------------------

    public static long gcd(long a,long b){
        if(b==0){
            return a;
        }

        return gcd(b,a%b);
    }
    public static void BFS(ArrayList<Integer>[] graph) {


    }

// This is an extension of method 2. Instead of moving one by one, divide the array in different sets
//where number of sets is equal to GCD of n and d and move the elements within sets.
//If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.
//Here is an example for n =12 and d = 3. GCD is 3 and


//     void leftRotate(int arr[], int d, int n)
//     {
//         /* To handle if d >= n */
//         d = d % n;
//         int i, j, k, temp;
//         int g_c_d = gcd(d, n);
//         for (i = 0; i < g_c_d; i++) {
//             /* move i-th values of blocks */
//             temp = arr[i];
//             j = i;
//             while (true) {
//                 k = j + d;
//                 if (k >= n)
//                     k = k - n;
//                 if (k == i)
//                     break;
//                 arr[j] = arr[k];
//                 j = k;
//             }
//             arr[j] = temp;
//         }
//     }


 }
// Fenwick / BinaryIndexed  Tree  USE IT - FenwickTree ft1=new FenwickTree(n);
