Pour deux entiers $x$ et $y$ ($x, y \geq 2$), nous dirons que $x$ est un générateur de $y$ si et seulement si $x$ peut être transformé en $y$ en effectuant l'opération suivante un certain nombre de fois (éventuellement zéro) :

• Choisir un diviseur $d$ ($d \geq 2$) de $x$, puis augmenter $x$ de $d$.

Par exemple :

• 3 est un générateur de 8 car nous pouvons effectuer les opérations suivantes : $3 \xrightarrow{d=3} 6 \xrightarrow{d=2} 8$ ;
• 4 est un générateur de 10 car nous pouvons effectuer les opérations suivantes : $4 \xrightarrow{d=4} 8 \xrightarrow{d=2} 10$ ;
• 5 n'est pas un générateur de 6 car nous ne pouvons pas transformer 5 en 6 avec l'opération ci-dessus.

Maintenant, Kevin vous donne un tableau $a$ composé de $n$ entiers distincts deux à deux ($a_i \geq 2$). Vous devez trouver un entier $x \geq 2$ tel que pour chaque $1 \leq i \leq n$, $x$ soit un générateur de $a_i$, ou déterminer qu'un tel entier n'existe pas.

Entrée

Chaque test contient plusieurs cas de test. La première ligne de l'entrée contient un entier unique $t$ ($1 \leq t \leq 10^4$) — le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un entier unique $n$ ($1 \leq n \leq 10^5$) — la longueur du tableau $a$.

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($2 \leq a_i \leq 4 \cdot 10^5$) — les éléments du tableau $a$. Il est garanti que les éléments sont distincts deux à deux.

Il est garanti que la somme de $n$ sur tous les cas de test n'excède pas $10^5$.

Sortie

Pour chaque cas de test, affichez un entier unique $x$ — l'entier que vous avez trouvé. Affichez $-1$ s'il n'existe pas de $x$ valide.

S'il existe plusieurs réponses, vous pouvez en afficher n'importe laquelle.

Exemples

Entrée 1

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

Sortie 1

2
-1
7
3

Remarque

Dans le premier cas de test, pour $x = 2$ :

• 2 est un générateur de 8, car nous pouvons effectuer les opérations suivantes : $2 \xrightarrow{d=2} 4 \xrightarrow{d=4} 8$ ;
• 2 est un générateur de 9, car nous pouvons effectuer les opérations suivantes : $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=3} 9$ ;
• 2 est un générateur de 10, car nous pouvons effectuer les opérations suivantes : $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=2} 8 \xrightarrow{d=2} 10$.

Dans le deuxième cas de test, on peut prouver qu'il est impossible de trouver un générateur commun pour les quatre entiers.