Dla dwóch liczb całkowitych $x$ oraz $y$ ($x, y \ge 2$) powiemy, że $x$ jest generatorem $y$ wtedy i tylko wtedy, gdy $x$ można przekształcić w $y$ poprzez wykonanie następującej operacji pewną liczbę razy (być może zero):

• Wybierz dzielnik $d$ ($d \ge 2$) liczby $x$, a następnie zwiększ $x$ o $d$.

Na przykład:

• 3 jest generatorem 8, ponieważ możemy wykonać następujące operacje: $3 \xrightarrow{d=3} 6 \xrightarrow{d=2} 8$;
• 4 jest generatorem 10, ponieważ możemy wykonać następujące operacje: $4 \xrightarrow{d=4} 8 \xrightarrow{d=2} 10$;
• 5 nie jest generatorem 6, ponieważ nie możemy przekształcić 5 w 6 za pomocą powyższej operacji.

Kevin daje Ci tablicę $a$ składającą się z $n$ parami różnych liczb całkowitych ($a_i \ge 2$). Musisz znaleźć liczbę całkowitą $x \ge 2$ taką, że dla każdego $1 \le i \le n$, $x$ jest generatorem $a_i$, lub określić, że taka liczba nie istnieje.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^4$) — liczbę przypadków testowych. Następuje opis przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 10^5$) — długość tablicy $a$.

Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 4 \cdot 10^5$) — elementy tablicy $a$. Gwarantuje się, że elementy są parami różne.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą $x$ — znalezioną liczbę. Wypisz $-1$, jeśli nie istnieje poprawna liczba $x$.

Jeśli istnieje wiele odpowiedzi, możesz wypisać dowolną z nich.

Przykład

Wejście 1

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

Wyjście 1

2
-1
7
3

Uwagi

W pierwszym przypadku testowym, dla $x = 2$:

• 2 jest generatorem 8, ponieważ możemy wykonać następujące operacje: $2 \xrightarrow{d=2} 4 \xrightarrow{d=4} 8$;
• 2 jest generatorem 9, ponieważ możemy wykonać następujące operacje: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=3} 9$;
• 2 jest generatorem 10, ponieważ możemy wykonać następujące operacje: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=2} 8 \xrightarrow{d=2} 10$.

W drugim przypadku testowym można udowodnić, że nie da się znaleźć wspólnego generatora dla tych czterech liczb.