## 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

$\forall&space;i&space;,\&space;i\epsilon&space;[1....n]&space;,\&space;gcd(x,a_{i})&space;=&space;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 a,a,a,......an.

$1&space;\leq&space;T&space;\leq&space;10$

$1&space;\leq&space;n&space;\leq&space;10^{5}$

### Output

for every case print one integer x in one line  .

Note: x should be greater than 1.

### Example

Input:335 7 2541 2 3 412Output:253

 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