D. Yet Another Array Problemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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) of integers $$$x$$$ and $$$y$$$. InputThe 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}$$$.OutputFor 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$$$.ExampleInput41146 6 12 12324 120 21042 4 6 10Output2553NoteIn 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$$$.