Little MS tiene una colección de $n$ cuchillos, y el $i$-ésimo cuchillo tiene una capacidad de corte de $a_i$. Necesita cortar un pastel gigante en porciones, pero no puede decidir qué cuchillos de su colección elegir para esta tarea tan importante.

Después de un tiempo, Little MS decidió elegir un subconjunto no vacío de cuchillos de manera uniforme al azar (de modo que cada subconjunto tiene una probabilidad de $\frac{1}{2^n-1}$ de ser elegido). Después utilizará todos los cuchillos elegidos en cualquier orden; un cuchillo con capacidad de corte $x$ cortará cada porción existente en $x$ porciones más pequeñas. Al final, Little MS tendrá $a_{i_1}\cdot\ldots\cdot a_{i_k}$ porciones, donde $i_1,\ldots,i_k$ son los índices de los cuchillos elegidos.

Ayuda a Little MS a determinar si existe un número $s$ tal que la probabilidad de que Little MS termine con exactamente $s$ porciones de pastel sea estrictamente mayor que el $50\%$.

Entrada

La primera línea contiene un único entero $t$ ($1\le t\le 10^4$): el número de casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ ($2\le n\le 2\cdot 10^5$): el número de cuchillos.

La segunda línea de cada caso de prueba contiene $n$ enteros $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$), donde $a_i$ es la capacidad de corte del $i$-ésimo cuchillo.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2\cdot 10^5$.

Salida

Para cada caso de prueba, imprime $-1$ si no existe ningún número $s$ adecuado.

En caso contrario, imprime un número $s$ tal que la probabilidad de que Little MS termine con exactamente $s$ porciones de pastel sea estrictamente mayor que el $50\%$.

Ejemplos

Entrada 1

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

Salida 1

-1
100
-1
1

Nota

En el primer caso de prueba, los productos posibles de todos los subconjuntos no vacíos de cuchillos son $2$, $3$ y $6$. Cada uno aparece una vez, por lo que ninguno se obtiene con una probabilidad estrictamente mayor que el $50\%$. Por tanto, la respuesta es $-1$.

En el segundo caso de prueba, los productos posibles de todos los subconjuntos no vacíos de cuchillos son $100$, $100$ y $10000$. El producto $100$ aparece en 2 de los 3 casos, por lo que su probabilidad es estrictamente mayor que el $50\%$. Por tanto, la respuesta es $100$.

En el tercer caso de prueba, los productos posibles de todos los subconjuntos no vacíos de cuchillos son $2$, $2$, $2$, $4$, $4$, $4$ y $8$. Ningún producto aparece más de la mitad de las veces, por lo que la respuesta es $-1$.