The MEX problem HackerEarth Question

 The MEX problem

Max. score: 100

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$

 

 

SAMPLE INPUT

 

1
4
1 2 4 8

SAMPLE OUTPUT

 

3

Explanation

Here, a = {1,2,4,8}. possible all gcd of 2 length sunsequence = {1,1,1,2,2,4} so MEX = 3.

      

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

Marking Scheme:Score is assigned if any testcase passes.

Allowed Languages:Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic