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.

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