L. 15 Prime
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abdelaleem has an array $$$a$$$ of $$$n$$$ integers and needs your assistance in finding the minimum positive integer $$$m$$$ such that $$$\text{gcd}(a_i, m) \geq 2$$$ for all $$$a_i$$$ in the array $$$a$$$.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10$$$) – the number of test cases.

For each test case:

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 5 \times 10^5)$$$ — the number of integers in the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(2 \leq a_i \leq 50)$$$ — the elements of the array $$$a$$$.

Output

For each test case, Output a single integer $$$m$$$ — the minimum positive integer such that $$$\text{gcd}(a_i, m) \geq 2$$$ for all $$$a_i$$$ in the array $$$a$$$.

Example
Input
4
2
4 3
1
2
2
7 47
7
3 4 6 7 8 9 10
Output
6
2
329
42