#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long modx = 998244353;
long double PI = 3.1415926535897;
const long long N = 1000100;
void solve();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  return 0;
}
long long ceils(long long x, long long y) { return x / y + ((x % y) != 0); }
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long x, long long y) {
  long long res = 1;
  for (long long i = 0; i < y; i++) {
    res = res * x % MOD;
  }
  return res;
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
bool COMP(pair<long long, long long> l, pair<long long, long long> r) {
  return l.second < r.second;
}
long long kadanesAlgo(vector<long long> a) {
  long long n = a.size();
  long long currMax = 0;
  long long mx = INT_MIN;
  for (long long i = 0; i < n; i++) {
    currMax += a[i];
    if (currMax <= a[i]) {
      currMax = a[i];
    }
    mx = max(currMax, mx);
  }
  return mx;
}
long long ask(long long x, long long y) {
  cout << "?"
       << " ";
  cout << x << " " << y << endl;
  long long s;
  cin >> s;
  return s;
}
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
bool is_sorted(vector<long long> a) {
  long long x = 0;
  for (long long i = 0; i < a.size() - 1; i++) {
    if (a[i] < a[i + 1]) x++;
  }
  return x == a.size() - 1;
}
bool check(string a, string b) {
  long long n = a.size(), m = b.size();
  if (a < b) {
    return true;
  }
  if (a > b) {
    return false;
  }
  for (long long i = 0; i < a.size(); i++) {
    if (a[i] > b[i]) {
      return false;
    } else if (a[i] < b[i]) {
      return true;
    }
  }
  return false;
}
bool isSubSequence(string a, string b, long long m, long long n) {
  long long j = 0;
  for (long long i = 0; i < n and j < m; i++)
    if (a[j] == b[i]) j++;
  return (j == m);
}
long long power(long long n, long long x) {
  long long ans = 1;
  for (long long i = 0; i < n; i++) {
    ans *= x;
  }
  return ans;
}
void solve() {
  long long n;
  cin >> n;
  vector<long long> a(n);
  long long x = 0, y = 0;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    if (i % 2) {
      x = gcd(a[i], x);
    } else
      y = gcd(a[i], y);
  }
  if (x == y) {
    cout << 0;
    return;
  }
  long long ans = y;
  for (long long i = 0; i < n; i++) {
    if (i % 2) {
      if (a[i] % y == 0) {
        ans = x;
      }
    }
  }
  if (ans == y) {
    cout << y;
    return;
  }
  for (long long i = 0; i < n; i++) {
    if (i % 2 == 0) {
      if (a[i] % x == 0) {
        cout << 0;
        return;
      }
    }
  }
  cout << ans;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long modx = 998244353;
long double PI = 3.1415926535897;
const long long N = 1000100;
void solve();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  return 0;
}
long long ceils(long long x, long long y) { return x / y + ((x % y) != 0); }
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long x, long long y) {
  long long res = 1;
  for (long long i = 0; i < y; i++) {
    res = res * x % MOD;
  }
  return res;
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
bool COMP(pair<long long, long long> l, pair<long long, long long> r) {
  return l.second < r.second;
}
long long kadanesAlgo(vector<long long> a) {
  long long n = a.size();
  long long currMax = 0;
  long long mx = INT_MIN;
  for (long long i = 0; i < n; i++) {
    currMax += a[i];
    if (currMax <= a[i]) {
      currMax = a[i];
    }
    mx = max(currMax, mx);
  }
  return mx;
}
long long ask(long long x, long long y) {
  cout << "?"
       << " ";
  cout << x << " " << y << endl;
  long long s;
  cin >> s;
  return s;
}
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
bool is_sorted(vector<long long> a) {
  long long x = 0;
  for (long long i = 0; i < a.size() - 1; i++) {
    if (a[i] < a[i + 1]) x++;
  }
  return x == a.size() - 1;
}
bool check(string a, string b) {
  long long n = a.size(), m = b.size();
  if (a < b) {
    return true;
  }
  if (a > b) {
    return false;
  }
  for (long long i = 0; i < a.size(); i++) {
    if (a[i] > b[i]) {
      return false;
    } else if (a[i] < b[i]) {
      return true;
    }
  }
  return false;
}
bool isSubSequence(string a, string b, long long m, long long n) {
  long long j = 0;
  for (long long i = 0; i < n and j < m; i++)
    if (a[j] == b[i]) j++;
  return (j == m);
}
long long power(long long n, long long x) {
  long long ans = 1;
  for (long long i = 0; i < n; i++) {
    ans *= x;
  }
  return ans;
}
void solve() {
  long long n;
  cin >> n;
  vector<long long> a(n);
  long long x = 0, y = 0;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    if (i % 2) {
      x = gcd(a[i], x);
    } else
      y = gcd(a[i], y);
  }
  if (x == y) {
    cout << 0;
    return;
  }
  long long ans = y;
  for (long long i = 0; i < n; i++) {
    if (i % 2) {
      if (a[i] % y == 0) {
        ans = x;
      }
    }
  }
  if (ans == y) {
    cout << y;
    return;
  }
  for (long long i = 0; i < n; i++) {
    if (i % 2 == 0) {
      if (a[i] % x == 0) {
        cout << 0;
        return;
      }
    }
  }
  cout << ans;
}

```