Para dos enteros $x$ e $y$ ($x, y \geq 2$), diremos que $x$ es un generador de $y$ si y solo si $x$ puede transformarse en $y$ realizando la siguiente operación un número determinado de veces (posiblemente cero):

• Elegir un divisor $d$ ($d \geq 2$) de $x$, y luego aumentar $x$ en $d$.

Por ejemplo:

• $3$ es un generador de $8$ ya que podemos realizar las siguientes operaciones: $3 \xrightarrow{d=3} 6 \xrightarrow{d=2} 8$;
• $4$ es un generador de $10$ ya que podemos realizar las siguientes operaciones: $4 \xrightarrow{d=4} 8 \xrightarrow{d=2} 10$;
• $5$ no es un generador de $6$ ya que no podemos transformar $5$ en $6$ con la operación anterior.

Ahora, Kevin te da un arreglo $a$ que consiste en $n$ enteros distintos entre sí ($a_i \geq 2$). Debes encontrar un entero $x \geq 2$ tal que para cada $1 \leq i \leq n$, $x$ sea un generador de $a_i$, o determinar que tal entero no existe.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea de la entrada contiene un único entero $t$ ($1 \leq t \leq 10^4$) — el número de casos de prueba. A continuación se describen los casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ ($1 \leq n \leq 10^5$) — la longitud del arreglo $a$.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($2 \leq a_i \leq 4 \cdot 10^5$) — los elementos del arreglo $a$. Se garantiza que los elementos son distintos entre sí.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $10^5$.

Salida

Para cada caso de prueba, imprime un único entero $x$ — el entero que encontraste. Imprime $-1$ si no existe un $x$ válido.

Si hay múltiples respuestas, puedes imprimir cualquiera de ellas.

Ejemplos

Entrada 1

4
3
8 9 10
4
2 3 4 5
2
147 154
5
3 6 8 25 100000

Salida 1

2
-1
7
3

Nota

En el primer caso de prueba, para $x = 2$:

• $2$ es un generador de $8$, ya que podemos realizar las siguientes operaciones: $2 \xrightarrow{d=2} 4 \xrightarrow{d=4} 8$;
• $2$ es un generador de $9$, ya que podemos realizar las siguientes operaciones: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=3} 9$;
• $2$ es un generador de $10$, ya que podemos realizar las siguientes operaciones: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=2} 8 \xrightarrow{d=2} 10$.

En el segundo caso de prueba, se puede demostrar que es imposible encontrar un generador común para los cuatro enteros.