You are given an array $A$ of $N$ positive and pairwise distinct integers.
You can permute the elements in any way you want.
The cost of an ordering $(A_1, A_2, \ldots, A_N)$ is defined as $(((A_1 \bmod A_2) \bmod A_3)......) \bmod A_N$ where $X \bmod Y$ means the remainder when $X$ is divided by $Y$.
You need to find the maximum cost which can be attained through any possible ordering of the elements.

-----Input:-----
- The first line contains $T$ denoting the number of test cases.
- The first line of each testcase contains a single integer $N$.
- The second line of each testcase contains $N$ space-separated integers, the elements of $A$.

-----Output:-----
- For each testcase, output the maximum possible cost in a new line.

-----Constraints-----
- $1 \leq T \leq 5*10^5$
- $2 \leq N \leq 5*10^5$
- $1 \leq A_i \leq 10^9$
- Sum of $N$ over all testcases is less than or equal to $10^6$
- All elements in a single testcase are distinct.

-----Subtasks-----
- 100 points : Original constraints.

-----Sample Input:-----
1
2
7 12

-----Sample Output:-----
7

-----Explanation:-----
The two possible ways to order the elements are [7, 12] and [12, 7]. In the first case, the cost is $7 \bmod 12 = 7$ and in the second case the cost is $12 \bmod 7 = 5$. Clearly the answer is 7.

见题面

见题面