Max Mod - Repovive Premier Round 4 | Repovive

9A. Max Mod

500 pts1s256 MB

You are given an array $a_1, \dots, a_n$ .

The closeness between two indices $1 \leq i \neq j \leq n$ is equal to $a_i \bmod a_j$ .

Find the maximum possible closeness between two indices in the given array.

Constraints

$1 \leq t \leq 10^4$
$2 \leq n \leq 2 \times 10^5$
$1 \leq a_i \leq 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

3
1 5 6

Case 2

4
2 2 5 1

Case 3

5
1 1 1 1 1

Explanation

Case 1

The closeness between indices 2 and 3 is 5, since $5 \bmod 6 = 5$ .

Case 2

The closeness between indices 1 and 3 is 2, since $2 \bmod 5 = 2$ .

Case 3

All numbers are equal, so the closeness between any two indices is 0, since $x \bmod x = 0$ .

Output

Case 1

Case 2

Case 3

You are given an array $a_1, \dots, a_n$ .

The closeness between two indices $1 \leq i \neq j \leq n$ is equal to $a_i \bmod a_j$ .

Find the maximum possible closeness between two indices in the given array.

$1 \leq t \leq 10^4$
$2 \leq n \leq 2 \times 10^5$
$1 \leq a_i \leq 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

The closeness between indices 2 and 3 is 5, since $5 \bmod 6 = 5$ .

The closeness between indices 1 and 3 is 2, since $2 \bmod 5 = 2$ .

All numbers are equal, so the closeness between any two indices is 0, since $x \bmod x = 0$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

9A. Max Mod

Constraints

Input

Output

Samples

9A. Max Mod

Constraints

Input

Output

Samples