Для двух целых чисел $x$ и $y$ ($x, y \ge 2$) будем говорить, что $x$ является генератором $y$ тогда и только тогда, когда $x$ можно преобразовать в $y$, выполнив следующую операцию некоторое (возможно, нулевое) количество раз:

• Выберите делитель $d$ ($d \ge 2$) числа $x$, затем увеличьте $x$ на $d$.

Например:

• $3$ является генератором $8$, так как мы можем выполнить следующие операции: $3 \xrightarrow{d=3} 6 \xrightarrow{d=2} 8$;
• $4$ является генератором $10$, так как мы можем выполнить следующие операции: $4 \xrightarrow{d=4} 8 \xrightarrow{d=2} 10$;
• $5$ не является генератором $6$, так как мы не можем преобразовать $5$ в $6$ с помощью указанной операции.

Кевин дает вам массив $a$, состоящий из $n$ попарно различных целых чисел ($a_i \ge 2$). Вам нужно найти целое число $x \ge 2$ такое, что для каждого $1 \le i \le n$ число $x$ является генератором $a_i$, или определить, что такого числа не существует.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке входных данных содержится целое число $t$ ($1 \le t \le 10^4$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит целое число $n$ ($1 \le n \le 10^5$) — длину массива $a$.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 4 \cdot 10^5$) — элементы массива $a$. Гарантируется, что элементы попарно различны.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $10^5$.

Выходные данные

Для каждого набора входных данных выведите одно целое число $x$ — найденное вами число. Выведите $-1$, если подходящего $x$ не существует.

Если существует несколько ответов, вы можете вывести любой из них.

Примеры

Входные данные 1

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

Выходные данные 1

2
-1
7
3

Примечание

В первом наборе входных данных для $x = 2$:

• $2$ является генератором $8$, так как мы можем выполнить следующие операции: $2 \xrightarrow{d=2} 4 \xrightarrow{d=4} 8$;
• $2$ является генератором $9$, так как мы можем выполнить следующие операции: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=3} 9$;
• $2$ является генератором $10$, так как мы можем выполнить следующие операции: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=2} 8 \xrightarrow{d=2} 10$.

Во втором наборе входных данных можно доказать, что невозможно найти общий генератор для этих четырех чисел.