← 返回题目列表

Codeforces · 1759/F

F. 所有可能的数字

中文机器翻译题面 查看原题

黑板上写着一个正数 $$$x$$$,长度为 $$$n$$$,基数为 $$$p$$$ ($$$2 \le p \le 10^9$$$)。数字 $$$x$$$ 以序列 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < p$$$) 的形式给出 - $$$x$$$ 的数字按从左到右的顺序(最重要到最不重要)。

Dmitry 非常喜欢这个数字系统的所有数字,因此他希望每个数字至少看到一次。

通过一次操作,他可以:

- 取黑板上写的任何数字 $$$x$$$,将其增加 $$$1$$$,并将新值 $$$x + 1$$$ 写在黑板上。

例如,$$$p=5$$$ 和 $$$x=234_5$$$。

- 最初,棋盘包含数字 $$$2$$$、$$$3$$$ 和 $$$4$$$;
- Dmitry 将数字 $$$234_5$$$ 增加 $$$1$$$ 并记下数字 $$$240_5$$$。黑板上有数字 $$$0, 2, 3, 4$$$;
- Dmitry 将数字 $$$240_5$$$ 增加 $$$1$$$ 并写下数字 $$$241_5$$$。现在棋盘包含从 $$$0$$$ 到 $$$4$$$ 的所有数字。

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

输入

输入的第一行包含一个整数 $$$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 < p$$$) — 以 $$$p$$$ 为基数的数字系统中 $$$x$$$ 的数字

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

输出

对于每个测试用例,打印一个整数 - Dmitry 获取板上从 $$$0$$$ 到 $$$p-1$$$ 的所有数字所需的最少操作数。

可以证明,这总是需要有限数量的操作。

示例

输入 #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
1
0
0
7
995
2
1
1
1
2