#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
using lll = __int128;
using vl = vector<ll>;
using LOOPVAR_TYPE = ll;
const ld EPS = 1e-9;
const ld PI = 3.14159265358979323846L;
const ll INF = 1070000000LL;
const ll MOD = 998244353LL;
void fast_io() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
}
ll lin() {
  ll x;
  cin >> x;
  return x;
}
string input() {
  string s;
  cin >> s;
  return s;
}
vl vin(int n) {
  vector<ll> v(n);
  for (LOOPVAR_TYPE i = LOOPVAR_TYPE(0); i < LOOPVAR_TYPE(n); i++) cin >> v[i];
  return v;
}
template <class T>
bool chmin(T& a, const T& b) {
  return (b < a) ? (a = b, true) : false;
}
template <class T>
bool chmax(T& a, const T& b) {
  return (a < b) ? (a = b, true) : false;
}
template <class T>
map<T, ll> freq(const vector<T>& v) {
  map<T, ll> ret;
  for (T x : v) ++ret[x];
  return ret;
}
template <class T>
vector<T> reversed(vector<T> v) {
  reverse((v).begin(), (v).end());
  return v;
}
template <class T>
vector<T> sorted(vector<T> v) {
  sort((v).begin(), (v).end());
  return v;
}
template <class T>
vector<T> sub(const vector<T>& v, int from, int to) {
  vector<T> ret;
  copy(&v[from], &v[to], back_inserter(ret));
  return ret;
}
template <class T>
string str(const T& x, int prec = 20) {
  stringstream ss;
  ss << setprecision(prec) << x;
  return ss.str();
}
template <class T>
string str(const vector<T>& v, int prec = 20) {
  stringstream ss;
  ss << setprecision(prec);
  for (LOOPVAR_TYPE i = LOOPVAR_TYPE(0); i < LOOPVAR_TYPE(ll((v).size())); i++)
    ss << v[i] << (i < ll((v).size()) - 1 ? " " : "");
  return ss.str();
}
template <class T>
void print1(T&& x, const string& end) {
  cout << str(x) << end;
}
void print() { print1("", "\n"); }
template <class T, class... U>
void print(T&& head, U&&... tail) {
  print1(head, " ");
  print(forward<U>(tail)...);
}
template <class T>
void eprint1(T&& x, const string& end) {
  cout << str(x) << end;
}
void eprint() { eprint1("", "\n"); }
template <class T, class... U>
void eprint(T&& head, U&&... tail) {
  eprint1(head, " ");
  eprint(forward<U>(tail)...);
}
template <class... T>
void quit(T&&... x) {
  print(forward<T>(x)...);
  exit(0);
}
void yn(bool cnd, const string& yes = "Yes", const string& no = "No") {
  if (cnd)
    print(yes);
  else
    print(no);
}
void zip(vl& v) {
  vl w = v;
  sort((w).begin(), (w).end());
  int n = unique((w).begin(), (w).end()) - w.begin();
  for (ll& x : v) x = lower_bound(&w[0], &w[n], x) - &w[0];
}
vl zipped(vl v) {
  zip(v);
  return v;
}
map<ll, ll> zipmap(vl v) {
  map<ll, ll> ret;
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
  for (LOOPVAR_TYPE i = LOOPVAR_TYPE(0); i < LOOPVAR_TYPE(ll((v).size())); i++)
    ret[v[i]] = i;
  return ret;
}
vl divisors(ll n) {
  vl ret;
  for (ll i = 1; i * i <= n; ++i) {
    if (n % i == 0) {
      ret.emplace_back(i);
      if (i * i < n) {
        ret.emplace_back(n / i);
      }
    }
  }
  sort((ret).begin(), (ret).end());
  return ret;
}
map<ll, ll> factorize(ll n) {
  map<ll, ll> ret;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      ll t = 0;
      while (n % i == 0) {
        ++t;
        n /= i;
      }
      ret[i] = t;
    }
  }
  if (n > 1) ret[n] = 1;
  return ret;
}
void solveOne() {
  int n = lin();
  vl d = sorted(vin(n));
  map<ll, ll> m;
  for (ll x : d) {
    auto f = factorize(x);
    for (auto [p, e] : f) {
      chmax(m[p], e);
    }
  }
  ll ans = 1;
  for (auto [p, e] : m) {
    ans *= pow(p, e);
    if (ll((m).size()) == 1) ans *= p;
  }
  auto ansd = divisors(ans);
  ansd = sub(ansd, 1, ll((ansd).size()) - 1);
  print(d == ansd ? ans : -1);
}
int main() {
  fast_io();
  int num_tc = 1;
  cin >> num_tc;
  for (LOOPVAR_TYPE tc = LOOPVAR_TYPE(1); tc < LOOPVAR_TYPE(num_tc + 1); tc++) {
    solveOne();
  }
}

### Prompt

Please formulate a CPP solution 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;
using ld = long double;
using ll = long long;
using lll = __int128;
using vl = vector<ll>;
using LOOPVAR_TYPE = ll;
const ld EPS = 1e-9;
const ld PI = 3.14159265358979323846L;
const ll INF = 1070000000LL;
const ll MOD = 998244353LL;
void fast_io() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
}
ll lin() {
  ll x;
  cin >> x;
  return x;
}
string input() {
  string s;
  cin >> s;
  return s;
}
vl vin(int n) {
  vector<ll> v(n);
  for (LOOPVAR_TYPE i = LOOPVAR_TYPE(0); i < LOOPVAR_TYPE(n); i++) cin >> v[i];
  return v;
}
template <class T>
bool chmin(T& a, const T& b) {
  return (b < a) ? (a = b, true) : false;
}
template <class T>
bool chmax(T& a, const T& b) {
  return (a < b) ? (a = b, true) : false;
}
template <class T>
map<T, ll> freq(const vector<T>& v) {
  map<T, ll> ret;
  for (T x : v) ++ret[x];
  return ret;
}
template <class T>
vector<T> reversed(vector<T> v) {
  reverse((v).begin(), (v).end());
  return v;
}
template <class T>
vector<T> sorted(vector<T> v) {
  sort((v).begin(), (v).end());
  return v;
}
template <class T>
vector<T> sub(const vector<T>& v, int from, int to) {
  vector<T> ret;
  copy(&v[from], &v[to], back_inserter(ret));
  return ret;
}
template <class T>
string str(const T& x, int prec = 20) {
  stringstream ss;
  ss << setprecision(prec) << x;
  return ss.str();
}
template <class T>
string str(const vector<T>& v, int prec = 20) {
  stringstream ss;
  ss << setprecision(prec);
  for (LOOPVAR_TYPE i = LOOPVAR_TYPE(0); i < LOOPVAR_TYPE(ll((v).size())); i++)
    ss << v[i] << (i < ll((v).size()) - 1 ? " " : "");
  return ss.str();
}
template <class T>
void print1(T&& x, const string& end) {
  cout << str(x) << end;
}
void print() { print1("", "\n"); }
template <class T, class... U>
void print(T&& head, U&&... tail) {
  print1(head, " ");
  print(forward<U>(tail)...);
}
template <class T>
void eprint1(T&& x, const string& end) {
  cout << str(x) << end;
}
void eprint() { eprint1("", "\n"); }
template <class T, class... U>
void eprint(T&& head, U&&... tail) {
  eprint1(head, " ");
  eprint(forward<U>(tail)...);
}
template <class... T>
void quit(T&&... x) {
  print(forward<T>(x)...);
  exit(0);
}
void yn(bool cnd, const string& yes = "Yes", const string& no = "No") {
  if (cnd)
    print(yes);
  else
    print(no);
}
void zip(vl& v) {
  vl w = v;
  sort((w).begin(), (w).end());
  int n = unique((w).begin(), (w).end()) - w.begin();
  for (ll& x : v) x = lower_bound(&w[0], &w[n], x) - &w[0];
}
vl zipped(vl v) {
  zip(v);
  return v;
}
map<ll, ll> zipmap(vl v) {
  map<ll, ll> ret;
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
  for (LOOPVAR_TYPE i = LOOPVAR_TYPE(0); i < LOOPVAR_TYPE(ll((v).size())); i++)
    ret[v[i]] = i;
  return ret;
}
vl divisors(ll n) {
  vl ret;
  for (ll i = 1; i * i <= n; ++i) {
    if (n % i == 0) {
      ret.emplace_back(i);
      if (i * i < n) {
        ret.emplace_back(n / i);
      }
    }
  }
  sort((ret).begin(), (ret).end());
  return ret;
}
map<ll, ll> factorize(ll n) {
  map<ll, ll> ret;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      ll t = 0;
      while (n % i == 0) {
        ++t;
        n /= i;
      }
      ret[i] = t;
    }
  }
  if (n > 1) ret[n] = 1;
  return ret;
}
void solveOne() {
  int n = lin();
  vl d = sorted(vin(n));
  map<ll, ll> m;
  for (ll x : d) {
    auto f = factorize(x);
    for (auto [p, e] : f) {
      chmax(m[p], e);
    }
  }
  ll ans = 1;
  for (auto [p, e] : m) {
    ans *= pow(p, e);
    if (ll((m).size()) == 1) ans *= p;
  }
  auto ansd = divisors(ans);
  ansd = sub(ansd, 1, ll((ansd).size()) - 1);
  print(d == ansd ? ans : -1);
}
int main() {
  fast_io();
  int num_tc = 1;
  cin >> num_tc;
  for (LOOPVAR_TYPE tc = LOOPVAR_TYPE(1); tc < LOOPVAR_TYPE(num_tc + 1); tc++) {
    solveOne();
  }
}

```