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.

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