#include <bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
void prin(long long int a, long long int b, long long int c,
          long long int maxi) {
  if (a == max(b, c))
    cout << "1 ";
  else if (a == maxi)
    cout << "0 ";
  else
    cout << max(b, c) - a + 1 << " ";
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.second > b.second);
}
long long int power(long long int x, long long int y) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
void solve() {
  long long int n;
  cin >> n;
  vector<long long int> a(n);
  for (long long int i = 0; i < (n); i++) cin >> a[i];
  int flag = 1;
  long long int egcd = a[0], ogcd = a[1];
  long long int omin = a[1], emin = a[1];
  for (long long int i = 0; i < (n); i++) {
    if (i % 2 == 0) {
      egcd = gcd(egcd, a[i]);
    } else
      ogcd = gcd(ogcd, a[i]);
  }
  int flag1 = 0;
  for (long long int i = 0; i < (n - 1); i++) {
    if (a[i] % egcd == 0 && a[i + 1] % egcd == 0) {
      flag1 = 1;
      break;
    }
  }
  int flag2 = 0;
  for (long long int i = 0; i < (n - 1); i++) {
    if (a[i] % ogcd == 0 && a[i + 1] % ogcd == 0) {
      flag2 = 1;
      break;
    }
  }
  if (flag1 == 0)
    cout << egcd << endl;
  else if (flag2 == 0)
    cout << ogcd << endl;
  else
    cout << 0 << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1, x;
  cin >> t;
  while (t--) {
    solve();
  }
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 int p = 1e9 + 7;
void prin(long long int a, long long int b, long long int c,
          long long int maxi) {
  if (a == max(b, c))
    cout << "1 ";
  else if (a == maxi)
    cout << "0 ";
  else
    cout << max(b, c) - a + 1 << " ";
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) {
  return (a.second > b.second);
}
long long int power(long long int x, long long int y) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
void solve() {
  long long int n;
  cin >> n;
  vector<long long int> a(n);
  for (long long int i = 0; i < (n); i++) cin >> a[i];
  int flag = 1;
  long long int egcd = a[0], ogcd = a[1];
  long long int omin = a[1], emin = a[1];
  for (long long int i = 0; i < (n); i++) {
    if (i % 2 == 0) {
      egcd = gcd(egcd, a[i]);
    } else
      ogcd = gcd(ogcd, a[i]);
  }
  int flag1 = 0;
  for (long long int i = 0; i < (n - 1); i++) {
    if (a[i] % egcd == 0 && a[i + 1] % egcd == 0) {
      flag1 = 1;
      break;
    }
  }
  int flag2 = 0;
  for (long long int i = 0; i < (n - 1); i++) {
    if (a[i] % ogcd == 0 && a[i + 1] % ogcd == 0) {
      flag2 = 1;
      break;
    }
  }
  if (flag1 == 0)
    cout << egcd << endl;
  else if (flag2 == 0)
    cout << ogcd << endl;
  else
    cout << 0 << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1, x;
  cin >> t;
  while (t--) {
    solve();
  }
}

```