You are given an array a of n integers. You take every subsequence of 2 lengths and the GCD of that subsequence and insert into a new array.

What is the MEX of the new array?

Note: The MEX of an array is equal to the smallest positive integer that is not present in the array. For example, MEX(1,2,4,2,3,6,7) = 5.

Input format

The ﬁrst line contains a single integer t denoting the number of test cases.
In each of the t test cases that follow contains 2 lines:
- The first line of each test case contains a single integer n denoting the size of the array.
- The second line contains n integers a1,a2,...,aN denoting array a.

Output format

Print a single integer denoting the MEX of the new array for each test case.

Constraints

\(1 <= t <= 20 \)

\(1 <= n <= 100000\)

\(1 <= a_{i} <= 100000\)