2つの整数 $x$ と $y$ ($x, y \ge 2$) について、$x$ が $y$ の generator であるとは、$x$ に対して以下の操作を0回以上繰り返すことで $y$ に変換できることを指します。

• $x$ の約数 $d$ ($d \ge 2$) を選び、$x$ を $x + d$ に置き換える。

例えば、

• 3 は 8 の generator です。なぜなら、以下の操作が可能だからです：$3 \xrightarrow{d=3} 6 \xrightarrow{d=2} 8$
• 4 は 10 の generator です。なぜなら、以下の操作が可能だからです：$4 \xrightarrow{d=4} 8 \xrightarrow{d=2} 10$
• 5 は 6 の generator ではありません。なぜなら、上記の操作で 5 を 6 に変換することはできないからです。

今、Kevin は $n$ 個の相異なる整数からなる配列 $a$ ($a_i \ge 2$) を与えます。 各 $1 \le i \le n$ に対して $x$ が $a_i$ の generator となるような整数 $x \ge 2$ を見つけるか、そのような整数が存在しないことを判定してください。

入力

各テストケースは複数のテストケースを含みます。入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 10^4$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、配列 $a$ の長さである整数 $n$ ($1 \le n \le 10^5$) が含まれます。 2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 4 \cdot 10^5$) が含まれます。要素はすべて相異なることが保証されています。

すべてのテストケースにおける $n$ の総和は $10^5$ を超えないことが保証されています。

出力

各テストケースについて、見つけた整数 $x$ を1つ出力してください。有効な $x$ が存在しない場合は $-1$ を出力してください。

答えが複数ある場合は、そのうちのどれを出力しても構いません。

入出力例

入力 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 の generator です。なぜなら、以下の操作が可能だからです：$2 \xrightarrow{d=2} 4 \xrightarrow{d=4} 8$
• 2 は 9 の generator です。なぜなら、以下の操作が可能だからです：$2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=3} 9$
• 2 は 10 の generator です。なぜなら、以下の操作が可能だからです：$2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=2} 8 \xrightarrow{d=2} 10$

2番目のテストケースでは、4つの整数の共通の generator を見つけることは不可能であることが証明できます。