A positive number $x$ of length $n$ in base $p$ ($2 \le p \le 10^9$) is written on the blackboard. The number $x$ is given as a sequence $a_1, a_2, \dots, a_n$ ($0 \le a_i < p$) — the digits of $x$ in order from left to right (most significant to least significant).

Dmitry is very fond of all the digits of this number system, so he wants to see each of them at least once.

In one operation, he can:

take any number $x$ written on the board, increase it by $1$, and write the new value $x + 1$ on the board.

For example, $p=5$ and $x=234_5$.

Initially, the board contains the digits $2$, $3$ and $4$;

Dmitry increases the number $234_5$ by $1$ and writes down the number $240_5$. On the board there are digits $0, 2, 3, 4$;

Dmitry increases the number $240_5$ by $1$ and writes down the number $241_5$. Now the board contains all the digits from $0$ to $4$.

Your task is to determine the minimum number of operations required to make all the digits from $0$ to $p-1$ appear on the board at least once.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 2 \cdot 10^3$) — the number of test cases. The descriptions of the input test cases follow.

The first line of description of each test case contains two integers $n$ ($1 \le n \le 100$) and $p$ ($2 \le p \le 10^9$) — the length of the number and the base of the number system.

The second line of the description of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < p$) — digits of $x$ in number system with base $p$

It is guaranteed that the number $x$ does not contain leading zeros (that is, $a_1>0$).


-----Output-----

For each test case print a single integer — the minimum number of operations required for Dmitry to get all the digits on the board from $0$ to $p-1$.

It can be shown that this always requires a finite number of operations.


-----Examples-----

Input
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1
Output
1
1
0
0
7
995
2
1
1
1
2


-----Note-----

None

Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms

Number theory

Mathematics

Data structures
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
t = int(input(''))
C = [0] * t
for i in range(t):
	LRX = input('').split(' ')
	n = int(LRX[0])
	p = int(LRX[1])
	A = [int(x) for x in input('').split(' ')]
	if n == 1:
		if A[0] == 2:
			C[i] = p - 2
		else:
			C[i] = p - 1
		continue
	qq = n - 2
	while qq >= 0 and A[qq] == p - 1:
		qq -= 1
	if qq >= 0:
		sp = (A[qq] + 1) % p
	else:
		sp = 1
	S = set(A)
	q = (A[-1] - 1) % p
	v = False
	while q in S:
		q = (q - 1) % p
		if q == A[-1]:
			v = True
			break
	if v:
		continue
	if q == 0:
		C[i] = p - A[-1]
	elif q < A[-1] and q == sp:
		w = False
		q = (q - 1) % p
		while q in S:
			q = (q - 1) % p
			if q == p - 1:
				w = True
				break
		if w:
			C[i] = p - A[-1]
		else:
			C[i] = p + q - A[-1]
	elif q < A[-1]:
		C[i] = p + q - A[-1]
	else:
		C[i] = q - A[-1]
for j in C:
	print(j)


testcase = int(input())
for _ in range(testcase):
	(n, p) = [int(num) for num in input().split()]
	arr = [int(num) for num in input().split()]
	arrs = set(arr)
	arr.insert(0, 0)
	first = arr[-1]
	for i in range(n - 1, -1, -1):
		if arr[i] == p - 1:
			continue
		comp = arr[i] + 1
		break
	tt = comp in arrs
	i = (first - 1 + p) % p
	while i in arrs and i != first:
		i = (i - 1 + p) % p
	if i == first:
		print(0)
		continue
	elif i > first or tt:
		ans = (i - first + p) % p
	else:
		arrs.add(comp)
		i = (first - 1 + p) % p
		while i in arrs and i != first:
			i = (i - 1 + p) % p
		ans = max((p - first) % p, (i - first + p) % p)
	print(ans)


t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	a.reverse()
	i = 1
	while i < n and a[i] == p - 1:
		i += 1
	loopx = a[i] + 1 if i < n else 1
	free = set(a)
	fin = p - 1
	cur = (a[0] - 1) % p
	while cur in free:
		fin -= 1
		if fin == 0:
			break
		cur = (cur - 1) % p
	free.add(loopx)
	free.add(0)
	cur2 = (a[0] - 1) % p
	fin2 = p - 1
	while cur2 in free:
		fin2 -= 1
		if fin2 == 0:
			break
		cur2 = (cur2 - 1) % p
	fin = min(fin, max(fin2, p - a[0]))
	print(fin)


for t in range(int(input())):
	(n, p) = map(int, input().split())
	A = list(map(int, input().split()))
	last = A[-1]
	T = set(A)
	if len(T) == p:
		print(0)
		continue
	S = list(T)
	S.sort()
	if len(S) > last and S[last] == last:
		cur = p - 1
		while True:
			if cur not in T:
				print(cur - last)
				break
			cur -= 1
	else:
		for i in range(n - 2, -1, -1):
			if A[i] != p - 1:
				T.add(A[i] + 1)
				break
		else:
			T.add(1)
		if len(T) == p:
			print(p - last)
			continue
		cur = last - 1
		while True:
			if cur not in T:
				print(max(p - last, p - last + cur))
				break
			cur -= 1


from sys import stdin, stdout
t = int(stdin.readline().strip())

def addWithCarry(digits, base):
	carry = 1
	result = set(digits)
	result.add(0)
	for i in range(len(digits) - 2, -1, -1):
		curr = digits[i] + carry
		result.add(curr % base)
		carry = curr // base
	while carry:
		result.add(carry % base)
		carry //= base
	return result
for test in range(t):
	(n, p) = map(int, stdin.readline().split())
	digits = list(map(int, stdin.readline().split()))
	upper_bound = p
	ss = set(digits)
	answer = 0
	while upper_bound - 1 in ss:
		upper_bound -= 1
	if upper_bound == 0:
		print(0)
		continue
	if upper_bound > digits[-1]:
		answer += upper_bound - digits[-1] - 1
		(upper_bound, digits[-1]) = (digits[-1], upper_bound - 1)
	while upper_bound - 1 in ss:
		upper_bound -= 1
	if upper_bound == 0:
		print(answer)
		continue
	answer += p - digits[-1]
	ss = addWithCarry(digits, p)
	while upper_bound - 1 in ss:
		upper_bound -= 1
	if upper_bound == 0:
		print(answer)
		continue
	answer += upper_bound - 1
	print(answer)


def solve():
	(n, p) = map(int, input().split())
	digits = list(map(int, input().split()))
	digit_set = set(digits)
	digit_sorted = sorted(list(digit_set))
	last = digits[-1]
	lift = False
	for i in range(len(digit_set)):
		if i == last:
			break
		if i not in digit_set:
			lift = True
	else:
		lift = True
	if lift:
		for i in range(n - 2, -1, -1):
			if digits[i] + 1 != p:
				digit_set.add(digits[i] + 1)
				break
		else:
			digit_set.add(1)
		digit_sorted = sorted(list(digit_set))
		out = p - last
		for i in range(len(digit_set) + 1):
			if last - i == 0:
				break
			if last - i not in digit_set:
				out += last - i
				break
		return out
	else:
		maxp = last
		for ith in range(1, len(digit_sorted) + 1):
			i = len(digit_sorted) - ith
			if digit_sorted[i] != p - ith:
				maxp = p - ith
				break
		return maxp - last
for _ in range(int(input())):
	print(solve())