黑板上写着一个正数 $$$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