You are given an array A containing N integers, and a positive integer M. Find the maximum value of
$A_{i} + A_{j} + ((A_{i} - A_{j}) \bmod M)$

across all pairs 1 ≤ i, j ≤ N.

Note that $x \bmod M$ refers to the smallest non-negative integer obtained as the remainder upon dividing x by M. For example$, 4 \bmod 3 = 1$ and $(-10) \bmod 3 = 2$.

------ Input Format ------

• The first line of input will contain a single integer T, the number of test cases. The description of test cases follows.
• Each test case consists of two lines of input.
• The first line of each test case contains two space-separated integers N and M.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.

------ Output Format ------

• For each test case, output on a new line the maximum value of $A_{i} + A_{j} + ((A_{i} - A_{j}) \bmod M)$.

------ Constraints ------

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 2\cdot 10^{5}$
$2 ≤ M ≤ 5\cdot 10^{8}$
$0 ≤ A_{i} ≤ 5\cdot 10^{8}$
- The sum of $N$ across all test cases won't exceed $2\cdot 10^{5}$.

------ subtasks ------

Subtask 1 (10 points):
The sum of $N$ across all test cases won't exceed $1000$
Subtask 2 (20 points):
$2 ≤ M ≤ 1000$
Subtask 3 (70 points):
Original constraints

----- Sample Input 1 ------
4
2 18
12 1
3 5
4 5 6
5 4
79 29 80 58 80
3 20
33 46 56

----- Sample Output 1 ------
24
15
162
112
----- explanation 1 ------
Test case $1$: There are $4$ possible pairs of indices to choose from. Their respective values are:
- $i = 1, j = 1$, giving $12 + 12 + ((12 - 12) \bmod 18) = 24 + 0 = 24$
- $i = 1, j = 2$, giving $12 + 1 + ((12 - 1) \bmod 18) = 13 + 11 = 24$
- $i = 2, j = 1$, giving $1 + 12 + ((1 - 12) \bmod 18) = 13 + 7 = 20$
- $i = 2, j = 2$, giving $1 + 1 + ((1 - 1) \bmod 18) = 2 + 0 = 2$

Of these, the largest value is $24$.

Test case $2$: There are $3\times 3 = 9$ choices for pairs $(i, j)$. Of these, one way to achieve the maximum is by choosing $i = 2, j = 3$, giving $5 + 6 + ((5 - 6) \bmod 5) = 11 + 4 = 15$.

Test case $3$: Picking $i = 1, j = 3$ gives a value of $79 + 80 + ((79 - 80) \bmod 4) = 159 + 3 = 162$, which is the largest possible.

Test case $4$: Picking $i = 3, j = 2$ gives a value of $56 + 46 + ((56 - 46) \bmod 20) = 102 + 10 = 112$, which is the largest possible.

见题面

见题面