GCDS - Sabbir and gcd problem

no tags 

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 a1, a2, a3, ... an

Taskin asked for a minimum integer number x (x > 1) such that gcd(x, a1) = 1, gcd(x, a2) = 1, ... gcd(x, an) = 1.

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

∀i, i ∈ [1...n], gcd(x, ai) = 1

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 a1, a2, a3, ... an.

Constraints

1 <= T <= 10

1 <= n <= 105

1 <= ai <= 107

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


Added by:sabbir
Date:2017-02-23
Time limit:0.400s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All