Sabbir is a little boy. He loves math very much. One day his friend Taskin gave him a very hard task. Taskin gave him n numbers a₁, a₂, a₃, ... a_n

Taskin asked for a minimum integer number x (x > 1) such that gcd(x, a₁) = 1, gcd(x, a₂) = 1, ... gcd(x, a_n) = 1.

In other words you have to find a minimum integer x (x > 1 ) such that

Note: gcd is greatest common divisor.

Input

In the first line there will be an integer T, denoting the number of test cases. Each test case is consists of 2 lines.

In the first line there will be n, denoting the number of integers and next line contains n space separated integers a₁, a₂, a₃, ... a_n.

Constraints

1 <= T <= 10

1 <= n <= 10⁵

1 <= a_i <= 10⁷

Output

for every case print one integer x in one line.

Note: x should be greater than 1.

Example

Input:
3
3
5 7 25
4
1 2 3 4
1
2

Output:
2
5
3