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 first 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$