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.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(list(set(a)))
	print(max(a[-1] * 2, a[-1] + a[-2] + (a[-1] - a[-2]) % m, a[-2] + a[-1] + (a[-2] - a[-1]) % m))


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	a = list(map(int, input().split()))
	mx = max(a)
	print(max([x + mx + (x - mx) % M for x in a]))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = sorted([int(x) for x in input().split()])
	max_c = a.count(a[-1])
	if max_c == n:
		print(2 * a[-1])
	else:
		(b, s) = (a[-1], a[-1 - max_c])
		print(max(2 * b, b + s + (b - s) % m, b + s + (s - b) % m))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	ma = max(l)
	l1 = []
	for i in l:
		if (ma - i) % m > (i - ma) % m:
			l1.append(ma + i + (ma - i) % m)
		else:
			l1.append(ma + i + (i - ma) % m)
	print(max(l1))


for testcases in range(int(input())):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()[:n]))
	ma = max(lst)
	l = []
	for i in lst:
		if (ma - i) % m > (i - ma) % m:
			l.append(ma + i + (ma - i) % m)
		else:
			l.append(ma + i + (i - ma) % m)
	print(max(l))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	lst = set(map(int, input().split()))
	lst = list(lst)
	lst.sort()
	lst = lst[::-1]
	c = lst[0]
	b = lst[1]
	md = (b - c) % m
	if md < 0:
		md += m
	print(max(2 * c, c + b + md))


a = int(input(''))
for i in range(a):
	(n, m) = [int(x) for x in input('').split()]
	t = [int(x) for x in input('').split()]
	k = sorted(list(set(t)))
	print(max(k[-1] * 2, k[-1] + k[-2] + (k[-1] - k[-2]) % m, k[-2] + k[-1] + (k[-2] - k[-1]) % m))


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	(a, b) = sorted(list(set(map(int, input().split()))), reverse=True)[0:2]
	print(max(a + b + (a - b) % M, a + b + (b - a) % M, a * 2))


T = int(input())
for _ in range(0, T):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a = [*set(a)]
	l = sorted(a)
	b = l[-1] * 2
	c = l[-1] + l[-2] + (l[-1] - l[-2]) % m
	d = l[-1] + l[-2] + (l[-2] - l[-1]) % m
	print(max(b, c, d))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	list1 = list(map(int, input().split()))
	a = max(list1)
	mp = 0
	for x in list1:
		al = max((a - x) % m, (x - a) % m) + x + a
		if mp < al:
			mp = al
	print(mp)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	m = 2 * a[n - 1]
	for i in range(n - 1, -1, -1):
		p = a[i] + a[n - 1] + (a[i] - a[n - 1]) % k
		if p > m:
			m = p
	print(m)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ma = max(l)
	value = 0
	for i in l:
		value = max(value, i + ma + (i - ma) % k)
	print(value)


t = input()
for c in range(0, int(t)):
	(n, m) = list(map(int, input().split()))
	p = list((int(ele) for ele in input().strip().split()))[:n]
	p.sort()
	k = p[n - 1]
	l = 0
	t = []
	for i in p:
		if i < k:
			t.append(i)
	if len(t) > 0:
		l = t[len(t) - 1]
	d = 2 * k
	c = 0
	if (k - l) % m > (l - k) % m:
		c += (k - l) % m
	else:
		c += (l - k) % m
	s = k + l + c
	if s > d:
		print(s)
	else:
		print(d)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ma = max(a)
	p = 0
	for i in range(n):
		x = max((a[i] - ma) % m, (ma - a[i]) % m)
		if a[i] + ma + x > p:
			p = a[i] + ma + x
	print(p)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	max_num = max(a)
	sec_li = []
	compare1 = max_num * 2
	for i in a:
		compare2 = max_num + i + max((max_num - i) % m, (i - max_num) % m)
		sec_li.append(compare2)
	print(max(max(sec_li), compare1))


tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	max_num = max(arr)
	ans = max_num * 2
	for j in arr:
		temp_ans = max_num + j + max((max_num - j) % m, (j - max_num) % m)
		ans = max(temp_ans, ans)
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lis = sorted(list(set(map(int, input().split()))))
	a = lis[-1]
	ma = -99999
	for i in lis:
		ma = max(ma, a + i + (i - a) % m)
	print(ma)


T = int(input())
for i in range(T):
	NM = input().split(' ')
	A = input().split(' ')
	n = int(A[0])
	for i in range(1, int(NM[0])):
		if int(A[i]) > n:
			n = int(A[i])
	m = -1
	for i in range(int(NM[0])):
		temp = n + int(A[i]) + (int(A[i]) - n) % int(NM[1])
		if temp > m:
			m = temp
	print(m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	a = 0
	(q, r) = (0, 0)
	for i in l:
		q = i + l[n - 1]
		r = i - l[n - 1]
		h = r % m
		a = max(a, h + q)
	print(a)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(sorted(set(map(int, input().split())), reverse=True))
	m = max(l[0] * 2, l[0] + l[1] + (l[1] - l[0]) % b)
	print(m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	k = list(set(l))
	k.sort()
	length = len(k)
	if length >= 2:
		maxm1 = 2 * k[length - 1]
		if k[length - 1] - k[length - 2] > m / 2:
			addn_factor = (k[length - 1] - k[length - 2]) % m
		else:
			addn_factor = (k[length - 2] - k[length - 1]) % m
		maxm2 = k[length - 1] + k[length - 2] + addn_factor
		print(max(maxm1, maxm2))
	else:
		print(2 * k[0])


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = set(map(int, input().split()))
	A = list(reversed(sorted(A)))
	m = max(A[0] * 2, A[0] + A[1] + (A[1] - A[0]) % M)
	print(m)


t = int(input().strip())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	val = max(arr)
	for i in arr:
		ans = max(ans, i + val + (i - val) % m)
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	result = []
	for i in a:
		result.append(i + a[-1] + (i - a[-1]) % m)
	print(max(result))


from itertools import combinations
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	l = []
	for i in a:
		x = i + a[-1] + (i - a[-1]) % m
		l.append(x)
	print(max(l))


def solve(q, w, n):
	ann = 0
	p = max(q)
	for i in range(n):
		o = q[i]
		w1 = p + o + (p - o) % w
		w2 = p + o + (o - p) % w
		w3 = max(w1, w2)
		if w3 > ann:
			ann = w3
	return ann
f = int(input())
for _ in range(f):
	(e, w) = map(int, input().split())
	q = list(map(int, input().split()))
	print(solve(q, w, e))


for i in range(int(input())):
	(x, y) = map(int, input().split())
	z = list(map(int, input().split()))
	t = max(z)
	s = []
	for l in range(0, len(z)):
		o = (t - z[l]) % y + t + z[l]
		p = (z[l] - t) % y + t + z[l]
		s.append(max(o, p))
	print(max(s))


for i in range(int(input())):
	(N, M) = map(int, input().split())
	L1 = list(map(int, input().split()))
	L2 = list(set(L1))
	L2.sort()
	D1 = max(L1)
	D2 = L2[-2]
	(X, Y) = (L1.index(D1), L1.index(D2))
	K1 = D1 + D2 + (D2 - D1) % M
	K2 = D1 + D2 + (D1 - D2) % M
	K3 = D1 + D1 + (D1 - D1) % M
	if K3 > K1 and K3 > K2:
		print(K3)
	elif K1 > K2:
		print(K1)
	else:
		print(K2)


T = int(input())
while T:
	T -= 1
	arr = input().split()
	arr = [int(i) for i in arr]
	(N, M) = (arr[0], arr[1])
	arr = input().split()
	arr = [int(i) for i in arr]
	maxi = 0
	for z in arr:
		if z >= maxi:
			maxi = z
	max_ans = 0
	for i in arr:
		ans1 = maxi + i + (maxi - i) % M
		ans2 = i + maxi + (i - maxi) % M
		if ans1 >= max_ans:
			max_ans = ans1
		if ans2 >= max_ans:
			max_ans = ans2
	print(max_ans)


T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	hena = list(map(int, input().split()))
	hena = list(set(hena))
	hena.sort()
	n = len(hena)
	one = (hena[n - 2] - hena[n - 1]) % m
	print(max(max(hena) * 2, one + hena[n - 1] + hena[n - 2]))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = [int(i) for i in input().split()]
	l.sort()
	j = l[n - 1]
	best = 0
	for i in range(n):
		cur = l[i] + j + (l[i] - j) % m
		if cur > best:
			best = cur
	print(best)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(set(list(map(int, input().split()))))
	a = [arr[0], arr[1]]
	a.sort()
	for i in arr[2:]:
		if i > a[0]:
			del a[0]
			a.append(i)
			a.sort()
	if m < a[1] - a[0]:
		print(2 * a[1])
	else:
		print(a[1] + a[0] + max((a[1] - a[0]) % m, (a[0] - a[1]) % m))


ans = ''
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ind = arr.index(max(arr))
	res = -float('inf')
	for i in range(n):
		res = max(res, arr[ind] + arr[i] + (arr[i] - arr[ind]) % m)
	ans += str(res) + '\n'
print(ans)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	d = list(map(int, input().strip().split()))[:n]
	mx = max(d)
	print(max([a + mx + (a - mx) % m for a in d]))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	mx = 0
	l.sort()
	for i in range(n):
		mx = max(mx, l[i] + l[-1] + max((l[i] - l[-1]) % m, (l[-1] - l[i]) % m))
	print(mx)


T = int(input())

def algo():
	(N, M) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')[:N]))
	A.sort(reverse=True)
	i = 0
	p = 0
	q = 1
	out = A[p] + A[p]
	while q < N:
		if A[p] - A[q] >= M / 2:
			out = A[p] + A[p]
			break
		elif A[p] - A[q] == 0:
			q += 1
		else:
			out = A[p] + A[q] + (M - A[p] + A[q])
			break
	print(out)
for i in range(T):
	algo()


M = 1000000007

def solve():
	(n, M) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l1.sort(reverse=True)
	ma = 0
	m = l1[0]
	for i in range(0, n):
		ma = max(ma, m + l1[i] + (l1[i] - m) % M)
	print(ma)
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = [int(x) for x in input().split()]
	l.sort()
	ans = 0
	for i in l:
		ans = max(ans, l[-1] + i + (i - l[-1]) % m)
	print(ans)


t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	j = l[n - 1]
	ma = 0
	for i in range(n):
		if l[i] + (l[i] - j) % m > ma:
			ma = l[i] + (l[i] - j) % m
	print(ma + j)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	res = 0
	for i in l:
		res = max(res, l[-1] + i + (i - l[-1]) % m)
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	m = max(arr)
	for el in arr:
		ans = max(ans, m + el + (el - m) % k)
	print(ans)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = float('-inf')
	mx = max(a)
	ind = a.index(mx)
	for i in range(n):
		ans = max(ans, a[i] + mx + (a[i] - mx) % m)
	print(ans)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	val = list(map(int, input().split()))
	val.sort()
	maxVal = val[-1]
	res = 0
	for a in val:
		res = max(res, a + maxVal + ((a - maxVal) % m + m) % m)
	print(res)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	s1 = arr[0] + arr[0]
	c = 0
	for i in range(0, len(arr) - 1):
		rem2 = (arr[i + 1] - arr[i]) % m
		rem1 = (arr[i] - arr[i + 1]) % m
		if rem1 > rem2:
			rem = rem1
		else:
			rem = rem2
		ans = arr[i] + arr[i + 1] + rem
		if ans > s1:
			s1 = ans
	print(s1)
	t -= 1


n = int(input())
while n > 0:
	n -= 1
	mx = -5555555555
	(a, m) = map(int, input().split())
	l = list(map(int, input().split()))
	mxele = max(l)
	for i in range(1, a + 1):
		mx = max(mx, mxele + l[i - 1] + (l[i - 1] - mxele) % m)
	print(mx)


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	Max_val = max(A)
	ans = 0
	for j in range(N):
		val = A[j] + Max_val + (A[j] - Max_val) % M
		if ans < val:
			ans = val
	print(ans)


T = int(input())
for _ in range(T):
	(N, M) = tuple([int(x) for x in input().split(' ')])
	lis = [int(x) for x in input().split(' ')]
	Aj = max(lis)
	lis2 = [x + Aj + (Aj - x) % M for x in lis] + [x + Aj + (x - Aj) % M for x in lis]
	print(max(lis2))


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	inp_list = list(map(int, input().split()))
	max_element = max(inp_list)
	print(max([i + max_element + (i - max_element) % m for i in inp_list]))
	t = t - 1


t = int(input())
for k in range(t):
	(n, M) = map(int, input().split())
	a = list(map(int, input().split()))
	m = max(a)
	print(max([x + m + (x - m) % M for x in a]))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	maxi = max(arr)
	res = 0
	for i in range(0, n):
		temp = maxi + arr[i] + (maxi - arr[i]) % m
		temp = max(temp, maxi + arr[i] + (arr[i] - maxi) % m)
		res = max(res, temp)
	print(res)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def solve():
	for _ in range(get_int()):
		(n, m) = get_ints()
		arr = get_list()
		ans = -1 * maxsize
		maxx = max(arr)
		for i in range(n):
			ans = max(ans, arr[i] + maxx + (arr[i] - maxx) % m, arr[i] + maxx + (maxx - arr[i]) % m)
		get_print_int(ans)
solve()


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	d = list(map(int, input().split()))
	dm = max(d)
	m = 0
	for i in range(l[0]):
		ans = d[i] + dm + (d[i] - dm) % l[1]
		if ans > m:
			m = ans
	print(m)


for i in range(int(input())):
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	mx = max(m)
	print(*max(([x + mx + (x - mx) % l[1]] for x in m)))


t = int(input())
for x in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ma = -1
	a.sort(reverse=True)
	o = a[0]
	for i in a:
		if o + i + (i - o) % m > ma:
			ma = o + i + (i - o) % m
	print(ma)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	diff = []
	res = -float('inf')
	for i in range(n):
		diff.append((a[i] - a[n - 1]) % m)
	for i in range(n):
		res = max(res, diff[i] + a[i] + a[n - 1])
	print(res)


from sys import stdin, stdout

def scan():
	return stdin.readline().strip()

def scanm():
	return map(int, scan().split())

def out(s):
	return stdout.write(str(s) + '\n')

def largest2(l):
	(a, b) = (-1, -1)
	for i in l:
		if i > a:
			(a, b) = (i, a)
		elif i != a and i > b:
			b = i
	return (a, b)
for _ in range(int(scan())):
	(n, m) = scanm()
	l = list(set(scanm()))
	(ai, aj) = largest2(l)
	if ai - aj > (aj - ai) % m:
		print(2 * ai)
	else:
		print(ai + aj + (aj - ai) % m)


from sys import stdin, stdout

def scan():
	return stdin.readline().strip()

def scanm():
	return map(int, scan().split())

def out(s):
	return stdout.write(str(s) + '\n')
from heapq import nlargest
for _ in range(int(scan())):
	(n, m) = scanm()
	l = list(set(scanm()))
	(ai, aj) = nlargest(2, l)
	if ai - aj > (aj - ai) % m:
		print(2 * ai)
	else:
		print(ai + aj + (aj - ai) % m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lis = list(map(int, input().split()))
	ma = -1
	a = max(lis)
	for i in lis:
		if a + i + (i - a) % m > ma:
			ma = a + i + (i - a) % m
	print(ma)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lis = list(map(int, input().split()))
	ma = -1
	lis.sort(reverse=True)
	a = lis[0]
	for i in lis:
		if a + i + (i - a) % m > ma:
			ma = a + i + (i - a) % m
	print(ma)


import itertools
t = int(input())
for y in range(t):
	(N, M) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	aj = l[0]
	max1 = 0
	for i in l:
		u = aj + i + (i - aj) % M
		if u > max1:
			max1 = u
	print(max1)


t = int(input())
while t > 0:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	a = list(map(int, input().split()[:n]))
	b = max(a)
	v = []
	for i in range(n):
		c = a[i] + b + (a[i] - b) % m
		v.append(c)
	print(max(v))
	t -= 1


def max_and_sec_max(l):
	(m, sm) = (-1, -1)
	for i in l:
		if i > m:
			sm = m
			m = i
		elif m > i > sm:
			sm = i
	return (m, sm)
for item in range(int(input())):
	(n, m) = map(int, input().split())
	a = map(int, input().split())
	(ai, aj) = max_and_sec_max(a)
	if ai - aj > (aj - ai) % m:
		print(2 * ai)
	else:
		print(ai + aj + (aj - ai) % m)


def max_and_sec_max(l):
	(m, sm) = (-1, -1)
	for i in l:
		if i > m:
			sm = m
			m = i
		elif m > i > sm:
			sm = i
	return (m, sm)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = map(int, input().split())
	(Ai, Aj) = max_and_sec_max(A)
	if Ai - Aj > (Aj - Ai) % M:
		print(2 * Ai)
	else:
		print(Ai + Aj + (Aj - Ai) % M)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = max(a)
	b = 0
	for j in range(n):
		temp = c + a[j] + (a[j] - c) % m
		b = max(b, temp)
	print(b)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	elements = list(map(int, input().strip().split()))[:n]
	a = 0
	k = max(elements)
	for j in range(n):
		temp = k + elements[j] + (elements[j] - k) % m
		a = max(a, temp)
	print(a)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	fm = []
	i = max(a)
	for j in range(len(a)):
		result = a[j] + i + (a[j] - i) % m
		fm.append(result)
	print(max(fm))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	a = max(l)
	g = max(([a + x + (x - a) % m] for x in l))
	print(g[0])


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	lis = list(map(int, input().split()))
	maximum = max(lis)
	ans = 0
	for j in lis:
		c = maximum + j + max((maximum - j) % m, (j - maximum) % m)
		if c > ans:
			ans = c
	print(ans)