## GCDS - Sabbir and gcd problem

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**_{1}, a_{2}, a_{3}, ... a_{n}Taskin asked for a minimum integer number * x* (

**x > 1**) such that

*.*

**gcd(x, a**_{1}) = 1, gcd(x, a_{2}) = 1, ... gcd(x, a_{n}) = 1In other words you have to find a minimum integer * x (x > 1 )* such that

∀i, i ∈ [1...n], gcd(x, a_{i}) = 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 _{1}, a_{2}, a_{3}, ... a_{n}**.

### Constraints

1 <= T <= 10

1 <= n <= 10^{5}

1 <= a_{i} <= 10^{7}

### 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 2Output: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 |