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.math.*;
    import java.io.*;
    import java.util.*;

    
//-------------------------------///////////////****/////////******//////////
//------------------------------------///**********//*****//********//*****//
//-----------------------------------///**********//*****//********//*****//
//----------------------------------///**********//*****//********//*****//
//---------------------------------///**********//*****//********//*****//
//--------------------------------///**********//*****//********//*****//
//--------------------------///**///**********//*****//********//*****//
//---------------------------/////***********/////////*******//////////

    
    public class CodeForces
    {
    	final static String no = "NO";
    	final static String yes = "YES";
    	static long count = 0;
    	
    	static public OutputWriter w = new OutputWriter(System.out);
    	static public FastScanner sc = new FastScanner();
    	

    	static HashMap<Integer,Integer> map = new HashMap<>();
    	
    	static Scanner fc = new Scanner(System.in);

//*******************************************Be SANSA**********************************************************
//************************************Don't stick to single approach********************************************	
//*****************************************You are a slow learner But you learn*********************************
//***************************************Don't fall in rating trap***********************************************
//**********************************Pain in temporary, regret remains forever************************************
    	
    	
        public static void main(String[] args) {
        	int test =sc.nextInt();
        	in:
        	while(test-->0) {
        		int n = sc.nextInt();
        		long[]arr= sc.longArray(n);
        		
        		
        		long g1 = arr[0];
        		long g2 = arr[1];
        		for(int i=2;i<n;i+=2) {
        			g1 = gcd(g1,arr[i]);
        		}
        		for(int i=3;i<n;i+=2) {
        			g2 = gcd(g2,arr[i]);
        		}
        		long d=0;
    			int check=-1;
    			if(g1!=1) {
    				d=g1;
    				check=1;
    				while(check<n) {
    					if(arr[check]%g1==0) {
    						d=0;
    						break;
    					}
    					check+=2;
    				}
    				
    			}
    			if(g2!=1 && d==0) {
    				d=g2;
    				check=0;
    				while(check<n) {
    					if(arr[check]%g2==0) {
    						d=0;
    						break;
    					}
    					check+=2;
    				}
    				
    			}
        		
        		w.writer.println(d);
        		
        		
        	}
        	w.writer.flush();	
        }
        
        static int sod(long  n) {
        	int res = 0;
        	while(n!=0) {
        		res+=n%10;
        		n = n/10;
        	}
			return res;
		}
		static class Pair {
            int visits, index;
            Pair(int visits, int index) {
                this.visits = visits;
                this.index = index;
            }
        }
        static public boolean checkBit(int n,int i){
            if((n>>i & 1)==1){
                return true;
            }else{
                return false;
            }
        }
        public static long pow(long a,long p)
        {
            long res=1;
            while(p>0)
            {
                if(p%2==1)
                {
                    p--;
                    res*=a;
                    res%=(long)1e9+7;
                }
                else
                {
                    a*=a;
                    a%=(long)1e9+7;
                    p/=2;
                }
            }
            return res;
        }
        static int gcd(int a, int b){
            if (a == 0)
                return b;
            return gcd(b % a, a);
        }
        static long gcd(long a, long b){
            if (a == 0)
                return b;
            return gcd(b % a, a);
        }
         
        // method to return LCM of two numbers
        static long lcm(long a, long b)
        {
            return (a / gcd(a, b)) * b;
        }
        static long getPairsCount(long[] arr, long sum)
        {
            Map<Long, Long> hm = new HashMap<>();
            int n = arr.length;
            long count = 0;
            for(int i =0;i<n;i++) {
            	if(hm.containsKey(sum - arr[i])) {
            		count+=hm.get(sum-arr[i]);
            	}
            	if(hm.get(arr[i])!=null) {
            		hm.put(arr[i], hm.get(arr[i])+1);
            	}
            	else {
            		hm.put(arr[i], 1l);
            	}
            }
            return count;
        }
        static long sumLong(int[]arr) {
        	long sum =0;
        	for(int x:arr) {
        		sum+=x;
        	}
        	return sum;
        }
        static boolean isEqualList(ArrayList<Integer> arr,ArrayList<Integer> temp){
            for(int i =0;i<arr.size();i++){
                if(arr.get(i)!=temp.get(i)){
                    return true;
                }
            }
            return false;
        }
    	static void sort(int[] arr) {
            Random rand = new Random();
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                int idx = rand.nextInt(n);
                if (idx == i) continue;
                arr[i] ^= arr[idx];
                arr[idx] ^= arr[i];
                arr[i] ^= arr[idx];
            }
            Arrays.sort(arr);
        }
     
        static void sort(long[] arr) {
            Random rand = new Random();
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                int idx = rand.nextInt(n);
                if (idx == i) continue;
                arr[i] ^= arr[idx];
                arr[idx] ^= arr[i];
                arr[i] ^= arr[idx];
            }
            Arrays.sort(arr);
        }
     
        static void sortDec(int[] arr) {
            Random rand = new Random();
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                int idx = rand.nextInt(n);
                if (idx == i) continue;
                arr[i] ^= arr[idx];
                arr[idx] ^= arr[i];
                arr[i] ^= arr[idx];
            }
            Arrays.sort(arr);
            int l = 0;
            int r = n - 1;
            while (l < r) {
                arr[l] ^= arr[r];
                arr[r] ^= arr[l];
                arr[l] ^= arr[r];
                l++;
                r--;
            }
        }
     
        static void sortDec(long[] arr) {
            Random rand = new Random();
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                int idx = rand.nextInt(n);
                if (idx == i) continue;
                arr[i] ^= arr[idx];
                arr[idx] ^= arr[i];
                arr[i] ^= arr[idx];
            }
            Arrays.sort(arr);
            int l = 0;
            int r = n - 1;
            while (l < r) {
                arr[l] ^= arr[r];
                arr[r] ^= arr[l];
                arr[l] ^= arr[r];
                l++;
                r--;
            }
        }
    	
    	
    	static int[] countInversions(int[]arr,int low,int high){
    		if(low==high) {
    			int base[] = new int[1];
    			base[0] = arr[low];
    			return base;
    		}
    		int mid = low+(high-low)/2;
    		int left[] = countInversions(arr,low,mid);
    		int right[] = countInversions(arr,mid+1,high);
    		int[]merged = merge(left,right);
    		return merged;
    	}
    	
    	
    	static int[] merge(int first[], int[]next) {
    		
    		int i = 0;
    		int j = 0;
    		int k = 0;
    		int[]merged = new int[first.length+next.length];
    		while(j<first.length && k<next.length) {
    			if(first[j]<=next[k]) {
    				merged[i++] = first[j++];
    			}else {
    				count += first.length -j;
    				merged[i++] = next[k++];
    				
    			}
    		}
    		while(j<first.length) {
    			merged[i++] = first[j++];
    		}
    		while(k<next.length) {
    			merged[i++] = next[k++];
    		}
    		return merged;
    	}
    	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());
    		}
    		long [] longArray(int n) {
    			long[] a=new long[n];
    			for(int i=0 ; i<n ; i++) a[i]=nextLong();
    			return a;
    		}
    		double nextDouble() {
    			return Double.parseDouble(next());
    		}
    	}
        static public class OutputWriter {
            private  final PrintWriter writer;
     
            public OutputWriter(OutputStream outputStream) {
                writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
            }
     
            public OutputWriter(Writer writer) {
                this.writer = new PrintWriter(writer);
            }
     
            public void print(Object... objects) {
                for (int i = 0; i < objects.length; i++) {
                    if (i != 0)
                        writer.print(' ');
                    writer.print(objects[i]);
                }
            }
     
            public void printLine(Object... objects) {
                print(objects);
                writer.println();
            }
     
            public void close() {
                writer.close();
            }
        }
     
     
    }