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.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;

public class Main {

    public static long gcd(long a, long b) {
        while (b != 0) {
            a %= b;

            long temp = a;
            a = b;
            b = temp;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        int tc = io.nextInt();
        for (int i = 0; i < tc; i++) {
            solve();
        }
        io.close();
    }

    private static void solve() throws Exception {
        int n = io.nextInt();
        long[] data = new long[n];
        for (int i = 0; i < n; i++) {
            data[i] = io.nextLong();
        }
        long evenGCD = data[0];
        for (int i = 0; i < n; i += 2) {
            evenGCD = gcd(evenGCD, data[i]);
        }
        boolean valid = true;
        for (int i = 1; i < n; i += 2) {
            if (data[i] % evenGCD == 0) {
                valid = false;
                break;
            }
        }
        if (valid) {
            io.println(evenGCD);
            return;
        }

        valid = true;
        long oddGCD = data[1];
        for (int i = 1; i < n; i += 2) {
            oddGCD = gcd(oddGCD, data[i]);
        }
        for (int i = 0; i < n; i += 2) {
            if (data[i] % oddGCD == 0) {
                valid = false;
                break;
            }
        }
        if (valid) {
            io.println(oddGCD);
        } else {
            io.println(0);
        }
    }


    static void sort(int[] a) {
        ArrayList<Integer> l = new ArrayList<>(a.length);
        for (int i : a) {
            l.add(i);
        }
        Collections.sort(l);
        for (int i = 0; i < a.length; i++) {
            a[i] = l.get(i);
        }
    }

    //-----------PrintWriter for faster output---------------------------------
    public static FastIO io = new FastIO();

    //-----------MyScanner class for faster input----------
    static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar, numChars;

        // standard input
        public FastIO() {
            this(System.in, System.out);
        }

        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }

        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }

        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) {
                    return -1; // end of file
                }
            }
            return buf[curChar++];
        }

        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > ' ');
            return res.toString();
        }

        public String nextLine() {
            int c;
            do {
                c = nextByte();
            } while (c < '\n');
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > '\n');
            return res.toString();
        }

        public int nextInt() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }

        public long nextLong() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }


        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
    //--------------------------------------------------------
}