MEX Dividend

curly_braces Criterion 2022 Round 19
Limits 1s, 512 MB

We define MEX Dividend of an array as the smallest positive integer not present in the array which is divisible by at least one of the elements of the array.

Given an array AA of size nn, your task is to print the MEX Dividend of the array.

Input

Input starts with a single integer T(1T105)T (1 \leq T \leq 10^5), number of test cases.

Each test case starts with an integer n(1n5105)n (1 \leq n \leq 5*10^5), the size of the array.

The next line contains nn space separated integers, A1,A2,,An(1Ai109)A_1, A_2, \dots, A_n(1 \leq A_i \leq 10^9), the elements of the array.

Note: It is guaranteed that sum of nn in all the test cases doesn’t exceed 10610^6.

Output

For each test case print an integer, the answer to that test case in a separate line.

Sample

InputOutput
3
2
1 2
3
2 3 4
5
2 3 4 5 6
3
6
8

Submit

Login to submit.

Statistics

42% Solution Ratio
tanvir03Earliest, 3w ago
masud_parvezppFastest, 0.0s
AndalusLightest, 25 kB
Being_GoromShortest, 464B
Toph uses cookies. By continuing you agree to our Cookie Policy.