#include <bits/stdc++.h>
using namespace std;
long long fact(long long num) {
  long long x = 1;
  for (long long i = 1; i <= num; ++i) {
    x = x * i;
  }
  return x;
}
void swap(long long *a, long long *b) {
  long long x = *b;
  *b = *a;
  *a = x;
}
int isPrime(long long num) {
  if (num <= 1) return 0;
  for (long long i = 2; i * i <= num; i++)
    if (num % i == 0) return 0;
  return 1;
}
long long power(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;
}
long long modFact(long long n, long long p) {
  if (n >= p) return 0;
  long long result = 1;
  for (long long i = 1; i <= n; i++) result = (result * i) % p;
  return result;
}
long long binarySearch(long long arr[], long long l, long long r, long long x) {
  if (r >= l) {
    long long mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
long long cnt = 0;
void fun(long long oldp, long long oldq, long long visit[21][21], long long m,
         long long n, long long count) {
  count++;
  visit[oldp][oldq] = count;
  cnt = max(cnt, count);
  for (long long p = 0; p < m; p++) {
    for (long long q = 0; q < n; q++) {
      if (p != oldp && q != oldq && p - q != oldp - oldq &&
          p + q != oldp + oldq && visit[p][q] == 0) {
        fun(p, q, visit, m, n, count);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long maxm = 0, ans = 0, sum = 0, count = 0, minm = 1000000000000;
  long long mx, my;
  long long m, n, k, t, x, y;
  long long f = 0;
  cin >> t;
  while (t--) {
    cin >> n;
    long long a[n];
    for (long long int c = 0; c < n; cin >> a[c++])
      ;
    ;
    vector<int> v;
    sort(a, a + n);
    long long x = a[0] * a[n - 1];
    for (int i = 0; i < n / 2; ++i) {
      if (a[i] * a[n - 1 - i] != x) {
        cout << -1 << endl;
        goto next;
      }
    }
    if (n % 2 != 0) {
      if (a[n / 2] * a[n - 1 - n / 2] != x) {
        cout << -1 << endl;
        goto next;
      }
    }
    for (int i = 2; i <= sqrt(x); i++) {
      if (x % i == 0) {
        if (x / i == i) {
          v.push_back(i);
        } else {
          v.push_back(i);
          v.push_back(x / i);
        }
      }
    }
    sort(v.begin(), v.end());
    if (v.size() != n) {
      cout << -1 << endl;
      goto next;
    }
    for (int i = 0; i < n; ++i) {
      if (v[i] != a[i]) {
        cout << -1 << endl;
        goto next;
      }
    }
    cout << x << endl;
  next:;
  }
  return 0;
}

### Prompt

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

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;
long long fact(long long num) {
  long long x = 1;
  for (long long i = 1; i <= num; ++i) {
    x = x * i;
  }
  return x;
}
void swap(long long *a, long long *b) {
  long long x = *b;
  *b = *a;
  *a = x;
}
int isPrime(long long num) {
  if (num <= 1) return 0;
  for (long long i = 2; i * i <= num; i++)
    if (num % i == 0) return 0;
  return 1;
}
long long power(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;
}
long long modFact(long long n, long long p) {
  if (n >= p) return 0;
  long long result = 1;
  for (long long i = 1; i <= n; i++) result = (result * i) % p;
  return result;
}
long long binarySearch(long long arr[], long long l, long long r, long long x) {
  if (r >= l) {
    long long mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
long long cnt = 0;
void fun(long long oldp, long long oldq, long long visit[21][21], long long m,
         long long n, long long count) {
  count++;
  visit[oldp][oldq] = count;
  cnt = max(cnt, count);
  for (long long p = 0; p < m; p++) {
    for (long long q = 0; q < n; q++) {
      if (p != oldp && q != oldq && p - q != oldp - oldq &&
          p + q != oldp + oldq && visit[p][q] == 0) {
        fun(p, q, visit, m, n, count);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long maxm = 0, ans = 0, sum = 0, count = 0, minm = 1000000000000;
  long long mx, my;
  long long m, n, k, t, x, y;
  long long f = 0;
  cin >> t;
  while (t--) {
    cin >> n;
    long long a[n];
    for (long long int c = 0; c < n; cin >> a[c++])
      ;
    ;
    vector<int> v;
    sort(a, a + n);
    long long x = a[0] * a[n - 1];
    for (int i = 0; i < n / 2; ++i) {
      if (a[i] * a[n - 1 - i] != x) {
        cout << -1 << endl;
        goto next;
      }
    }
    if (n % 2 != 0) {
      if (a[n / 2] * a[n - 1 - n / 2] != x) {
        cout << -1 << endl;
        goto next;
      }
    }
    for (int i = 2; i <= sqrt(x); i++) {
      if (x % i == 0) {
        if (x / i == i) {
          v.push_back(i);
        } else {
          v.push_back(i);
          v.push_back(x / i);
        }
      }
    }
    sort(v.begin(), v.end());
    if (v.size() != n) {
      cout << -1 << endl;
      goto next;
    }
    for (int i = 0; i < n; ++i) {
      if (v[i] != a[i]) {
        cout << -1 << endl;
        goto next;
      }
    }
    cout << x << endl;
  next:;
  }
  return 0;
}

```