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.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
import java.io.*;
public class Main {
    // Graph
    // prefix sums
    //inputs
    public static void main(String args[])throws Exception{
        Input sc=new Input();
        precalculates p=new precalculates();
        StringBuilder sb=new StringBuilder();
        int t=sc.readInt();
        for(int f=0;f<t;f++){
            int n=sc.readInt();
            long a[]=sc.readArrayLong();
            boolean b=false;
            long val=0;
            int d[]=new int[n];
            for(int i=0;i<n;i++){
                b=true;
                for(int j=0;j<n;j++){
                    if(a[j]%a[i]==0){
                        d[j]=1;
                    }else{
                        d[j]=-1;
                    }
                }
                for(int j=0;j<n-1;j++){
                    if(d[j]==d[j+1]){
                        b=false;
                        break;
                    }
                }
                if(b){
                    val=a[i];
                    break;
                }
            }
            sb.append(val+"\n");
        }
        System.out.print(sb);
    }
}
class Input{
    BufferedReader br;
    StringTokenizer st;
    Input(){
        br=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
    }
    public int[] readArray() throws Exception{
        st=new StringTokenizer(br.readLine());
        int a[]=new int[st.countTokens()];
        for(int i=0;i<a.length;i++){
            a[i]=Integer.parseInt(st.nextToken());
        }
        return a;
    }
    public long[] readArrayLong() throws Exception{
        st=new StringTokenizer(br.readLine());
        long a[]=new long[st.countTokens()];
        for(int i=0;i<a.length;i++){
            a[i]=Long.parseLong(st.nextToken());
        }
        return a;
    }
    public int readInt() throws Exception{
        st=new StringTokenizer(br.readLine());
        return Integer.parseInt(st.nextToken());
    }
    public long readLong() throws Exception{
        st=new StringTokenizer(br.readLine());
        return Long.parseLong(st.nextToken());
    }
    public String readString() throws Exception{
        return br.readLine();
    }
    public int[][] read2dArray(int n,int m)throws Exception{
        int a[][]=new int[n][m];
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                a[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        return a;
    }
}
class precalculates{
    public int[] prefixSumOneDimentional(int a[]){
        int n=a.length;
        int dp[]=new int[n];
        for(int i=0;i<n;i++){
            if(i==0)
                dp[i]=a[i];
            else
                dp[i]=dp[i-1]+a[i];
        }
        return dp;
    }
    public int[] postSumOneDimentional(int a[]) {
        int n = a.length;
        int dp[] = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1)
                dp[i] = a[i];
            else
                dp[i] = dp[i + 1] + a[i];
        }
        return dp;
    }
    public int[][] prefixSum2d(int a[][]){
        int n=a.length;int m=a[0].length;
        int dp[][]=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=a[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            }
        }
        return dp;
    }
    public long pow(long a,long b){
        long mod=1000000007;
        long ans=0;
        if(b<=0)
            return 1;
        if(b%2==0){
            ans=pow(a,b/2)%mod;
            return ((ans%mod)*(ans%mod))%mod;
        }else{
            return ((a%mod)*(ans%mod))%mod;
        }
    }

}
class GraphInteger{
    HashMap<Integer,vertex> vtces;
    class vertex{
        HashMap<Integer,Integer> children;
        public vertex(){
            children=new HashMap<>();
        }
    }
    public GraphInteger(){
        vtces=new HashMap<>();
    }
    public void addVertex(int a){
        vtces.put(a,new vertex());
    }
    public void addEdge(int a,int b,int cost){
        if(!vtces.containsKey(a)){
            vtces.put(a,new vertex());
        }
        if(!vtces.containsKey(b)){
            vtces.put(b,new vertex());
        }
        vtces.get(a).children.put(b,cost);
//        vtces.get(b).children.put(a,cost);
    }
    public boolean isCyclicDirected(){
        boolean isdone[]=new boolean[vtces.size()+1];
        boolean check[]=new boolean[vtces.size()+1];
        for(int i=1;i<=vtces.size();i++) {
            if (!isdone[i] && isCyclicDirected(i,isdone, check)) {
                return true;
            }
        }
        return false;
    }
    private boolean isCyclicDirected(int i,boolean isdone[],boolean check[]){
        if(check[i])
            return true;
        if(isdone[i])
            return false;
        check[i]=true;
        isdone[i]=true;
        Set<Integer> set=vtces.get(i).children.keySet();
        for(Integer ii:set){
            if(isCyclicDirected(ii,isdone,check))
                return true;
        }
        check[i]=false;
        return false;
    }
}
class union_find {
    int n;
    int[] sz;
    int[] par;

    union_find(int nval) {
        n = nval;
        sz = new int[n + 1];
        par = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int x) {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    boolean find(int a, int b) {
        return root(a) == root(b);
    }

    int union(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        if (ra == rb)
            return 0;
        if(a==b)
            return 0;
        if (sz[a] > sz[b]) {
            int temp = ra;
            ra = rb;
            rb = temp;
        }
        par[ra] = rb;
        sz[rb] += sz[ra];
        return 1;
    }
}





