CF1759F.All Possible Digits

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 \lt 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.

一个正整数 $x$（在 $p$ 进制下，其中 $2 \le p \le 10^9$）被写在黑板上，其长度为 $n$。该数 $x$ 以序列 $a_1, a_2, \dots, a_n$（其中 $0 \le a_i < p$）的形式给出——即 $x$ 在 $p$ 进制下的各位数字，从左到右（从最高位到最低位）排列。

德米特里非常喜爱该进制系统中的所有数字，因此他希望黑板上至少出现每个数字 $0$ 到 $p-1$ 各一次。

每次操作中，他可以执行以下操作之一：

• 任取黑板上的一个数 $x$，将其加 $1$，并将新值 $x + 1$ 写在黑板上。

例如，当 $p = 5$ 且 $x = 234_5$ 时：

• 最初，黑板上包含数字 $2$、$3$ 和 $4$；
• 德米特里将 $234_5$ 加 $1$，写下 $240_5$；此时黑板上的数字为 $0$、$2$、$3$、$4$；
• 德米特里再将 $240_5$ 加 $1$，写下 $241_5$；此时黑板上已包含 $0$ 至 $4$ 的所有数字。

你的任务是确定所需的最少操作次数，使得黑板上至少出现每个数字 $0$ 到 $p-1$ 各一次。

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 \lt 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 \gt 0$).

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^3$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的描述第一行为两个整数 $n$（$1 \le n \le 100$）和 $p$（$2 \le p \le 10^9$），分别表示数字的位数及所用进制。

每个测试用例的描述第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \lt p$），表示 $x$ 在 $p$ 进制下的各位数字。

保证数字 $x$ 不含前导零（即 $a_1 \gt 0$）。

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.

对于每个测试用例，输出一个整数——Dmitry 在黑板上得到从 $0$ 到 $p-1$ 的所有数字所需的最少操作次数。

可以证明，这总是只需要有限次操作。