Với hai số nguyên $x$ và $y$ ($x, y \ge 2$), ta nói $x$ là một generator (bộ tạo) của $y$ nếu và chỉ nếu $x$ có thể biến đổi thành $y$ bằng cách thực hiện thao tác sau một số lần (có thể bằng không):

• Chọn một ước số $d$ ($d \ge 2$) của $x$, sau đó tăng $x$ lên $d$ đơn vị.

Ví dụ:

• $3$ là một generator của $8$ vì ta có thể thực hiện các thao tác sau: $3 \xrightarrow{d=3} 6 \xrightarrow{d=2} 8$;
• $4$ là một generator của $10$ vì ta có thể thực hiện các thao tác sau: $4 \xrightarrow{d=4} 8 \xrightarrow{d=2} 10$;
• $5$ không phải là một generator của $6$ vì ta không thể biến đổi $5$ thành $6$ bằng thao tác trên.

Bây giờ, Kevin cho bạn một mảng $a$ gồm $n$ số nguyên phân biệt ($a_i \ge 2$). Bạn cần tìm một số nguyên $x \ge 2$ sao cho với mỗi $1 \le i \le n$, $x$ là một generator của $a_i$, hoặc xác định rằng không tồn tại số nguyên như vậy.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $t$ ($1 \le t \le 10^4$) — số lượng bộ dữ liệu. Tiếp theo là mô tả các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($1 \le n \le 10^5$) — độ dài của mảng $a$.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 4 \cdot 10^5$) — các phần tử trong mảng $a$. Đảm bảo rằng các phần tử là phân biệt.

Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất $x$ — số nguyên mà bạn tìm được. In ra $-1$ nếu không tồn tại $x$ thỏa mãn.

Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
-1
7
3

Ghi chú

Trong bộ dữ liệu đầu tiên, với $x = 2$:

• $2$ là một generator của $8$, vì ta có thể thực hiện các thao tác sau: $2 \xrightarrow{d=2} 4 \xrightarrow{d=4} 8$;
• $2$ là một generator của $9$, vì ta có thể thực hiện các thao tác sau: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=3} 9$;
• $2$ là một generator của $10$, vì ta có thể thực hiện các thao tác sau: $2 \xrightarrow{d=2} 4 \xrightarrow{d=2} 6 \xrightarrow{d=2} 8 \xrightarrow{d=2} 10$.

Trong bộ dữ liệu thứ hai, có thể chứng minh rằng không thể tìm được một generator chung cho bốn số nguyên đó.