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 

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,......an.

 

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-0.699s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All