Little MS has a collection of $n$ knives, and the $i$-th knife has a cutting power of $a_i$. She needs to cut a giant cake into pieces, but she can’t decide which knives to choose from her collection for this very important job.

After some time, Little MS decided that she will choose a non-empty subset of knives uniformly at random (so every subset has a chance of $\frac{1}{2^n-1}$ to be chosen). Then she will use all the chosen knives in any order; a knife with cutting power of $x$ will cut every current slice into $x$ smaller ones. In the end, Little MS will end up with $a_{i_1}\cdot\ldots\cdot a_{i_k}$ slices, where $i_1,\ldots,i_k$ are the indices of the chosen knives.

Help Little MS determine if there is a number $s$ such that the probability of Little MS ending up with exactly $s$ slices of cake is strictly greater than $50\%$.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot10^5$) — the number of knives.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$), where $a_i$ is the cutting power of the $i$-th knife.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

Output

For each test case, output $-1$ if there is no suitable number $s$.

Otherwise, output a number $s$ such that the probability that Little MS ends up with exactly $s$ cake slices is strictly greater than $50\%$.

Examples

Input 1

4
2
2 3
2
100 100
3
2 2 2
4
1 1 1 1

Output 1

-1
100
-1
1

Note

In the first test case, the possible products over all non-empty subsets of knives are $2$, $3$, and $6$. Each of them appears once, so none of them is obtained with a probability strictly greater than $50\%$. Therefore, the answer is $-1$.

In the second test case, the possible products over all non-empty subsets of knives are $100$, $100$, and $10000$. The product $100$ appears in $2$ out of $3$ cases, so its probability is strictly greater than $50\%$. Therefore, the answer is $100$.

In the third test case, the possible products over all non-empty subsets of knives are $2$, $2$, $2$, $4$, $4$, $4$, and $8$. No product appears more than half of the time, so the answer is $-1$.