不恋尘世浮华，不写红尘纷扰，不叹世道苍凉，不惹情思哀怨，闲看花开，静待花落，冷暖自知，干净如始。

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

Your task is to find the minimum possible integer xx 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 tt independent queries.

Input

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

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

The second line of the query contains nn integers d1,d2,…,dnd1,d2,…,dn (2≤di≤1062≤di≤106), where didi is the ii-th divisor of the guessed number. It is guaranteed that all values didi 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 xx that the given list of divisors is the list of almost all its divisors, print -1. Otherwise print the minimum possible xx.

Example

Input

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

Output

48 4 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<map> #include<algorithm> #include<iomanip> #include<queue> #include<set> #include<stack> using namespace std; long long a[305]; int main() { int t,n,flag; cin >> t; while (t--) { flag = 1; long long i; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; sort(a , a + n ); int z= 0, y = n-1; long long p = a[0] * a[n-1]; for (i = 2; i * i <= p; i++) { if (p % i == 0) { if (a[z] != i || a[y] != p / i) { flag = 0; break; } else { z++; y--; } } } if (z <= y) flag = 0; if (flag) cout<<p<<endl; else cout<<"-1"<<endl; } return 0; }