#include <bits/stdc++.h>
using namespace std;
bool isvowel(char c) {
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' ||
      c == 'E' || c == 'I' || c == 'O' || c == 'U')
    return true;
  return false;
}
bool prime[5000001];
int spf[5000001];
vector<int> primes;
void sieve() {
  memset(prime, true, sizeof(prime));
  for (int p = 2; p * p <= 5000000; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= 5000000; i += p) {
        prime[i] = false;
        if (spf[i] == 0) spf[i] = p;
      }
    }
  }
  for (int p = 2; p <= 5000000; p++)
    if (prime[p]) primes.push_back(p);
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long fast_exp(long long x, long long n) {
  long long ans = 1;
  while (n) {
    if (n & 1) ans *= x;
    n = n >> 1;
    x = x * x;
  }
  return ans;
}
long long mod_exp(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
void solve() {
  long long n;
  cin >> n;
  long long a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  ;
  sort(a, a + n);
  long long count = 0;
  long long number = a[0] * a[n - 1];
  for (long long i = 2; i * i <= number; i++) {
    if (number % i == 0) count += 2;
    if (i * i == number) count--;
  }
  for (long long i = 0; i < n; i++) {
    if (number % a[i] != 0) {
      cout << "-1"
           << "\n";
      return;
    }
  }
  if (count == n)
    cout << number << "\n";
  else
    cout << "-1"
         << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
bool isvowel(char c) {
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' ||
      c == 'E' || c == 'I' || c == 'O' || c == 'U')
    return true;
  return false;
}
bool prime[5000001];
int spf[5000001];
vector<int> primes;
void sieve() {
  memset(prime, true, sizeof(prime));
  for (int p = 2; p * p <= 5000000; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= 5000000; i += p) {
        prime[i] = false;
        if (spf[i] == 0) spf[i] = p;
      }
    }
  }
  for (int p = 2; p <= 5000000; p++)
    if (prime[p]) primes.push_back(p);
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long fast_exp(long long x, long long n) {
  long long ans = 1;
  while (n) {
    if (n & 1) ans *= x;
    n = n >> 1;
    x = x * x;
  }
  return ans;
}
long long mod_exp(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
void solve() {
  long long n;
  cin >> n;
  long long a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  ;
  sort(a, a + n);
  long long count = 0;
  long long number = a[0] * a[n - 1];
  for (long long i = 2; i * i <= number; i++) {
    if (number % i == 0) count += 2;
    if (i * i == number) count--;
  }
  for (long long i = 0; i < n; i++) {
    if (number % a[i] != 0) {
      cout << "-1"
           << "\n";
      return;
    }
  }
  if (count == n)
    cout << number << "\n";
  else
    cout << "-1"
         << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

```