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$$$.

Mental Monumental (Easy Version)

Examples