CF2167D Yet Another Array Problem

You are given an integer $ n $ and an array $ a $ of length $ n $ . Find the smallest integer $ x $ ( $ 2 \le x \le 10^{18} $ ) such that there exists an index $ i $ ( $ 1 \le i \le n $ ) with $ \gcd $ $ ^{\text{∗}} $ $ (a_i, x) = 1 $ . If no such $ x $ exists within the range $ [2,10^{18}] $ , output $ -1 $ . $ ^{\text{∗}} $ $ \gcd(x, y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ .

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each of the following $ t $ test cases consists of two lines: The first line contains a single integer $ n $ ( $ 1 \le n \le 10^{5} $ ) — the length of the array. The second line contains $ n $ space-separated integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{18} $ ). It is guaranteed that the total sum of $ n $ across all test cases does not exceed $ 10^{5} $ .

For each test case, output a single integer: the smallest $ x $ ( $ 2 \le x \le 10^{18} $ ) such that there exists an index $ i $ with $ \gcd(a_i, x) = 1 $ . If there is no such $ x $ in the range $ [2,10^{18}] $ , print $ -1 $ .

In the first test case, $ \gcd(2,1)=1 $ , which is the smallest number satisfying the condition. In the second test case: - $ \gcd(2,6)=2 $ , $ \gcd(2,12)=2 $ , so $ 2 $ cannot be the answer. - $ \gcd(3,6)=3 $ , $ \gcd(3,12)=3 $ , so $ 3 $ cannot be the answer. - $ \gcd(4,6)=2 $ , $ \gcd(4,12)=4 $ , so $ 4 $ cannot be the answer. - $ \gcd(5,6)=1 $ , so the answer is $ 5 $ . In the third test case: - $ \gcd(2,24)=2 $ , $ \gcd(2,120)=2 $ , $ \gcd(2,210)=2 $ , so $ 2 $ cannot be the answer. - $ \gcd(3,24)=3 $ , $ \gcd(3,120)=3 $ , $ \gcd(3,210)=3 $ , so $ 3 $ cannot be the answer. - $ \gcd(4,24)=4 $ , $ \gcd(4,120)=4 $ , $ \gcd(4,210)=2 $ , so $ 4 $ cannot be the answer. - $ \gcd(5,24)=1 $ , so the answer is $ 5 $ . In the fourth test case: - $ \gcd(2,2)=2 $ , $ \gcd(2,4)=2 $ , $ \gcd(2,6)=2 $ , $ \gcd(2,10)=2 $ , so $ 2 $ cannot be the answer. - $ \gcd(3,2)=1 $ , so the answer is $ 3 $ .