#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (a > b) swap(a, b);
  return a == 0 ? b : gcd(b % a, a);
}
long long gcd(long long a, long long b) {
  if (a > b) swap(a, b);
  return a == 0 ? b : gcd(b % a, a);
}
int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
inline int pow(int a, int b) {
  int ans = 1;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)b)); ((i))++) ans *= a;
  return ans;
}
inline long long pow(long long a, long long b) {
  long long ans = 1;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)b)); ((i))++) ans *= a;
  return ans;
}
inline long long pow(int a, long long b) {
  long long ans = 1;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)b)); ((i))++) ans *= a;
  return ans;
}
inline long long pow(long long a, int b) {
  long long ans = 1;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)b)); ((i))++) ans *= a;
  return ans;
}
template <typename T, typename U>
inline bool amin(T &x, U y) {
  return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
  return (x < y) ? (x = y, true) : false;
}
template <typename C>
inline void _cin(C &c) {
  cin >> c;
}
template <typename T, typename U>
inline void _cin(pair<T, U> &p) {
  cin >> p.first;
  cin >> p.second;
}
template <typename C>
inline void _cout(const C &c) {
  cout << c;
}
template <typename T, typename U>
inline void _cout(const pair<T, U> &p) {
  cout << p.first << ' ' << p.second;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u) {
  _cin(t);
  in(u...);
}
void out() { cout << endl; }
template <typename T, class... U>
void out(const T &t, U... u) {
  _cout(t);
  if (sizeof...(u)) cout << ' ';
  out(u...);
}
template <typename C>
inline void in(vector<C> &v, int N = -1) {
  if (((int)(v).size()) != 0) {
    int M = (N == -1) ? ((int)(v).size()) : N;
    for (int((i)) = ((int)0); ((i)) < ((int)((int)M)); ((i))++) _cin(v[i]);
  } else {
    C c;
    for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++)
      v.push_back((_cin(c), c));
  }
}
template <typename C>
inline void in(C v[], int N) {
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) _cin(v[i]);
}
template <typename C>
inline void out(const vector<C> &v, int N = -1) {
  int M = (N == -1) ? ((int)(v).size()) : N;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)M)); ((i))++) {
    cout << ((i) ? " " : "");
    _cout(v[i]);
  }
  cout << endl;
}
template <typename C>
inline void out(C v[], int N) {
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) {
    cout << ((i) ? " " : "");
    _cout(v[i]);
  }
  cout << endl;
}
template <typename C>
inline void vector_debug(const vector<C> &v, int N = -1) {
  cout << "{";
  int M = (N == -1) ? ((int)(v).size()) : N;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)M)); ((i))++) {
    cout << ((i) ? ", " : "");
    _cout(v[i]);
  }
  cout << "}";
}
template <typename C>
inline void vector_debug(C v[], int N) {
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) {
    cout << "{";
    cout << ((i) ? ", " : "");
    _cout(*(v + i));
  }
  cout << "}";
}
void dbg_out() { cout << endl; }
template <typename T, class... U>
void dbg_out(const T &t, U... u) {
  _cout(t);
  if (sizeof...(u)) cout << ", ";
  dbg_out(u...);
}
template <typename C, class... U>
void dbg_out(const vector<C> &v, U... u) {
  vector_debug(v);
  if (sizeof...(u)) cout << ", ";
  dbg_out(u...);
}
template <typename C, class... U>
void dbg_out(const vector<vector<C>> &v, U... u) {
  cout << "{ ";
  for (int((i)) = ((int)0); ((i)) < ((int)((int)((int)(v).size()))); ((i))++) {
    if (i) cout << ", ";
    vector_debug(v[i]);
  }
  cout << " }";
  if (sizeof...(u)) cout << ", ";
  dbg_out(u...);
}
template <typename C>
inline C vmax(const vector<C> &v) {
  C n = v[0];
  for (int((i)) = ((int)0); ((i)) < ((int)((int)((int)(v).size()))); ((i))++)
    amax(n, v[i]);
  return n;
}
template <typename C>
inline C vmax(C v[], int N) {
  C n = v[0];
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) amax(n, v[i]);
  return n;
}
template <typename C>
inline C vmin(const vector<C> &v) {
  C n = v[0];
  for (int((i)) = ((int)0); ((i)) < ((int)((int)((int)(v).size()))); ((i))++)
    amin(n, v[i]);
  return n;
}
template <typename C>
inline C vmin(C v[], int N) {
  C n = v[0];
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) amin(n, v[i]);
  return n;
}
template <typename C>
inline C vsum(const vector<C> &v) {
  C n = 0;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)((int)(v).size()))); ((i))++)
    n += v[i];
  return n;
}
template <typename C>
inline C vsum(C v[], int N) {
  C n = 0;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) n += v[i];
  return n;
}
inline long long madd(long long a, long long b) { return (a + b) % 998244353; }
inline long long msub(long long a, long long b) {
  return (a + 998244353 - b) % 998244353;
}
inline long long mmul(long long a, long long b) {
  return ((a % 998244353) * (b % 998244353)) % 998244353;
}
long long mpow(long long a, long long b) {
  if (b == 0)
    return 1;
  else if (b == 1)
    return a % 998244353;
  else if (b % 2 == 0) {
    long long hlf = mpow(a, b / 2);
    return (hlf * hlf) % 998244353;
  } else {
    long long hlf = mpow(a, b / 2);
    return (mmul(hlf, hlf) * a) % 998244353;
  }
}
inline long long mdiv(long long a, long long b) {
  return mmul(a, mpow(b, 998244353 - 2));
}
int main() {
  int T;
  in(T);
  for (int((hoge)) = ((int)0); ((hoge)) < ((int)((int)T)); ((hoge))++) {
    int N;
    in(N);
    vector<long long> v(N);
    in(v, N);
    sort((v).begin(), (v).end());
    int flg = 1;
    long long ans = v[0] * v[N - 1];
    for (int i = 1;; i++) {
      if (i > N - 1 - i) break;
      if (v[i] * v[N - 1 - i] != ans) {
        flg = 0;
        break;
      }
    }
    if (flg == 0) {
      out(-1);
      continue;
    }
    int cnt = 0;
    auto it = v.begin();
    for (long long i = 2; i * i <= ans; i++) {
      if (ans % i == 0) {
        if (i != *it) {
          flg = 0;
          break;
        } else {
          it++;
          cnt++;
        }
      }
    }
    if (flg == 0 || (N + 1) / 2 != cnt) {
      out(-1);
    } else {
      out(ans);
    }
  }
}

### Prompt

Please create a solution in cpp to the following problem:

We guessed some integer number x. You are given a list of almost all its divisors. Almost all means that there are all divisors except 1 and x in the list.

Your task is to find the minimum possible integer x that can be the guessed number, or say that the input data is contradictory and it is impossible to find such number.

You have to answer t independent queries.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 25) — the number of queries. Then t queries follow.

The first line of the query contains one integer n (1 ≤ n ≤ 300) — the number of divisors in the list.

The second line of the query contains n integers d_1, d_2, ..., d_n (2 ≤ d_i ≤ 10^6), where d_i is the i-th divisor of the guessed number. It is guaranteed that all values d_i are distinct.

Output

For each query print the answer to it.

If the input data in the query is contradictory and it is impossible to find such number x that the given list of divisors is the list of almost all its divisors, print -1. Otherwise print the minimum possible x.

Example

Input


2
8
8 2 12 6 4 24 16 3
1
2


Output


48
4

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (a > b) swap(a, b);
  return a == 0 ? b : gcd(b % a, a);
}
long long gcd(long long a, long long b) {
  if (a > b) swap(a, b);
  return a == 0 ? b : gcd(b % a, a);
}
int lcm(int a, int b) { return (a / gcd(a, b)) * b; }
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
inline int pow(int a, int b) {
  int ans = 1;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)b)); ((i))++) ans *= a;
  return ans;
}
inline long long pow(long long a, long long b) {
  long long ans = 1;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)b)); ((i))++) ans *= a;
  return ans;
}
inline long long pow(int a, long long b) {
  long long ans = 1;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)b)); ((i))++) ans *= a;
  return ans;
}
inline long long pow(long long a, int b) {
  long long ans = 1;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)b)); ((i))++) ans *= a;
  return ans;
}
template <typename T, typename U>
inline bool amin(T &x, U y) {
  return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
  return (x < y) ? (x = y, true) : false;
}
template <typename C>
inline void _cin(C &c) {
  cin >> c;
}
template <typename T, typename U>
inline void _cin(pair<T, U> &p) {
  cin >> p.first;
  cin >> p.second;
}
template <typename C>
inline void _cout(const C &c) {
  cout << c;
}
template <typename T, typename U>
inline void _cout(const pair<T, U> &p) {
  cout << p.first << ' ' << p.second;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u) {
  _cin(t);
  in(u...);
}
void out() { cout << endl; }
template <typename T, class... U>
void out(const T &t, U... u) {
  _cout(t);
  if (sizeof...(u)) cout << ' ';
  out(u...);
}
template <typename C>
inline void in(vector<C> &v, int N = -1) {
  if (((int)(v).size()) != 0) {
    int M = (N == -1) ? ((int)(v).size()) : N;
    for (int((i)) = ((int)0); ((i)) < ((int)((int)M)); ((i))++) _cin(v[i]);
  } else {
    C c;
    for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++)
      v.push_back((_cin(c), c));
  }
}
template <typename C>
inline void in(C v[], int N) {
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) _cin(v[i]);
}
template <typename C>
inline void out(const vector<C> &v, int N = -1) {
  int M = (N == -1) ? ((int)(v).size()) : N;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)M)); ((i))++) {
    cout << ((i) ? " " : "");
    _cout(v[i]);
  }
  cout << endl;
}
template <typename C>
inline void out(C v[], int N) {
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) {
    cout << ((i) ? " " : "");
    _cout(v[i]);
  }
  cout << endl;
}
template <typename C>
inline void vector_debug(const vector<C> &v, int N = -1) {
  cout << "{";
  int M = (N == -1) ? ((int)(v).size()) : N;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)M)); ((i))++) {
    cout << ((i) ? ", " : "");
    _cout(v[i]);
  }
  cout << "}";
}
template <typename C>
inline void vector_debug(C v[], int N) {
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) {
    cout << "{";
    cout << ((i) ? ", " : "");
    _cout(*(v + i));
  }
  cout << "}";
}
void dbg_out() { cout << endl; }
template <typename T, class... U>
void dbg_out(const T &t, U... u) {
  _cout(t);
  if (sizeof...(u)) cout << ", ";
  dbg_out(u...);
}
template <typename C, class... U>
void dbg_out(const vector<C> &v, U... u) {
  vector_debug(v);
  if (sizeof...(u)) cout << ", ";
  dbg_out(u...);
}
template <typename C, class... U>
void dbg_out(const vector<vector<C>> &v, U... u) {
  cout << "{ ";
  for (int((i)) = ((int)0); ((i)) < ((int)((int)((int)(v).size()))); ((i))++) {
    if (i) cout << ", ";
    vector_debug(v[i]);
  }
  cout << " }";
  if (sizeof...(u)) cout << ", ";
  dbg_out(u...);
}
template <typename C>
inline C vmax(const vector<C> &v) {
  C n = v[0];
  for (int((i)) = ((int)0); ((i)) < ((int)((int)((int)(v).size()))); ((i))++)
    amax(n, v[i]);
  return n;
}
template <typename C>
inline C vmax(C v[], int N) {
  C n = v[0];
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) amax(n, v[i]);
  return n;
}
template <typename C>
inline C vmin(const vector<C> &v) {
  C n = v[0];
  for (int((i)) = ((int)0); ((i)) < ((int)((int)((int)(v).size()))); ((i))++)
    amin(n, v[i]);
  return n;
}
template <typename C>
inline C vmin(C v[], int N) {
  C n = v[0];
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) amin(n, v[i]);
  return n;
}
template <typename C>
inline C vsum(const vector<C> &v) {
  C n = 0;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)((int)(v).size()))); ((i))++)
    n += v[i];
  return n;
}
template <typename C>
inline C vsum(C v[], int N) {
  C n = 0;
  for (int((i)) = ((int)0); ((i)) < ((int)((int)N)); ((i))++) n += v[i];
  return n;
}
inline long long madd(long long a, long long b) { return (a + b) % 998244353; }
inline long long msub(long long a, long long b) {
  return (a + 998244353 - b) % 998244353;
}
inline long long mmul(long long a, long long b) {
  return ((a % 998244353) * (b % 998244353)) % 998244353;
}
long long mpow(long long a, long long b) {
  if (b == 0)
    return 1;
  else if (b == 1)
    return a % 998244353;
  else if (b % 2 == 0) {
    long long hlf = mpow(a, b / 2);
    return (hlf * hlf) % 998244353;
  } else {
    long long hlf = mpow(a, b / 2);
    return (mmul(hlf, hlf) * a) % 998244353;
  }
}
inline long long mdiv(long long a, long long b) {
  return mmul(a, mpow(b, 998244353 - 2));
}
int main() {
  int T;
  in(T);
  for (int((hoge)) = ((int)0); ((hoge)) < ((int)((int)T)); ((hoge))++) {
    int N;
    in(N);
    vector<long long> v(N);
    in(v, N);
    sort((v).begin(), (v).end());
    int flg = 1;
    long long ans = v[0] * v[N - 1];
    for (int i = 1;; i++) {
      if (i > N - 1 - i) break;
      if (v[i] * v[N - 1 - i] != ans) {
        flg = 0;
        break;
      }
    }
    if (flg == 0) {
      out(-1);
      continue;
    }
    int cnt = 0;
    auto it = v.begin();
    for (long long i = 2; i * i <= ans; i++) {
      if (ans % i == 0) {
        if (i != *it) {
          flg = 0;
          break;
        } else {
          it++;
          cnt++;
        }
      }
    }
    if (flg == 0 || (N + 1) / 2 != cnt) {
      out(-1);
    } else {
      out(ans);
    }
  }
}

```