This is the easy version of this problem. The difference between the versions is that in this version, you are required to find only the value of $f(a)$.

For any array $[c_1, c_2, \ldots, c_m]$, we define $f(c)$ as the maximum possible $\operatorname{mex}(c)$$^{\text{∗}}$ that can be achieved by performing the following operation exactly once:

• Choose an integer array $[b_1, b_2, \ldots, b_m]$ such that $b_i \ge 1$ for all $1 \le i \le m$;
• Set $c_i := c_i \, \bmod \, b_i$$^{\text{†}}$ for every $1 \le i \le m$.

You are given an array $a$ consisting of $n$ non-negative integers. Determine the value of $f(a)$.

$^{\text{∗}}$$\operatorname{mex}(c)$ denotes the minimum excluded (MEX) of the integers in $c$. For example, $\operatorname{mex}([2,2,1])=0$ because $0$ does not belong to the array, and $\operatorname{mex}([0,3,1,2])=4$ because $0$, $1$, $2$, and $3$ appear in the array, but $4$ does not.$^{\text{†}}$$u \bmod v$ denotes the remainder from dividing $u$ by $v$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. It is guaranteed that the sum of $\max(a_1,a_2,\ldots,a_n)$ over all test cases does not exceed $10^6$.

Output

For each testcase, output a single integer — the value of $f(a)$.

Note

For the first testcase, choosing $b = [1, 2, 3, 4]$ leaves $a$ unchanged and we have $\operatorname{mex}(a) = 4$.

For the second testcase, choosing $b = [3, 3]$ makes $a = [0, 1]$. Thus, we have $\operatorname{mex}(a) = 2$.