题目描述

给定一个长度为 $n$，进制为 $p(2≤p≤10^9)$ 的正整数 $x$，它被写在黑板上。数 $x$ 按顺序从左到右（从高位到低位）表示为序列 $a_1,a_2,...,a_n(0≤a_i<p)$。

光头强很喜欢这个数字系统的所有数字，所以他想至少看到每个数字一次。

在一次操作中，他可以：

以 $x+1$ 的形式取任何数字 $x$ 并写入新值 $x+1$。

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

初始时，黑板上有数字 $2,3$ 和 $4$； 光头强将数字 $234_5$ 增加 $1$，写下数字 $240_5$。现在黑板上有数字 $0,2,3$ 和 $4$； 光头强将数字 $2405$ 增加 $1$，写下数字 $241_5$。现在黑板上有数字 $0$ 到 $4$。

你的任务是确定使所有 $0$ 到 $p-1$ 的数字至少出现一次所需的最小操作次数。

输入格式

输入的第一行包含一个整数 $t(1≤t≤2⋅10^3)$ — 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的描述的第一行包含两个整数 $n(1≤n≤100)$ 和 $p(2≤p≤10^9)$ — 数字的长度和数字系统的进制。

每个测试用例的描述的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n (0≤a_i<p)$ — 数字 $x$ 在进制为 $p$ 的数字系统中的每个位上的数字。

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

输出格式

对于每个测试用例，输出一个整数 — 光头强需要进行的最小操作数，以便在黑板上获得从 $0$ 到 $p−1$ 的所有数字。

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

测试样例

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

1
1
0
0
7
995
2
1
1
1
2

样例说明