有$$$n$$$箱子;第 $$$i$$$ 个箱子最初包含 $$$a_i$$$ 硬币。对于每个箱子,您可以选择任何非负($$$0$$$ 或更多)数量的硬币添加到该箱子中,但有一个限制:所有箱子中的硬币总数必须至少为 $$$k$$$。
当你向箱子里添加完金币后,贪婪的 Monocarp 就会来,他想要金币。他会一一拿走箱子,由于他很贪心,所以他总是会选择硬币数量最多的箱子。一旦他拿走的箱子中的金币总数至少为 $$$k$$$,Monocarp 就会停止。
你希望 Monocarp 拿走尽可能少的硬币,所以你必须以这样的方式向箱子添加硬币,这样,当 Monocarp 停止拿走箱子时,他将恰好拥有 $$$k$$$ 硬币。计算您需要添加的最少硬币数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 50$$$; $$$1 \le k \le 10^7$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$)。
输出
对于每个测试用例,打印一个整数 - 您必须添加的最小硬币数量,以便当 Monocarp 停止拿走箱子时,他正好拥有 $$$k$$$ 硬币。可以证明,在问题的约束下,总是可能的。
示例
输入 #1
4 5 4 4 1 2 3 2 5 10 4 1 2 3 2 2 10 1 1 3 8 3 3 3
输出 #1
0 1 8 2
注意
在示例的第一个测试用例中,您不必添加任何硬币。当 Monocarp 到达时,他会拿走装有 $$$4$$$ 硬币的箱子,因此他将恰好拥有 $$$4$$$ 硬币。
在示例的第二个测试用例中,您可以将 $$$1$$$ 硬币添加到第 $$$4$$$ 个箱子中,因此,当 Monocarp 到达时,他会拿走一个装有 $$$4$$$ 硬币的箱子,然后是另一个装有 $$$4$$$ 硬币的箱子,最后是一个装有 $$$2$$$ 硬币的箱子。
在示例的第三个测试用例中,您可以将 $$$3$$$ 硬币添加到 $$$1$$$-st 箱子中,将 $$$5$$$ 硬币添加到 $$$2$$$-nd 箱子中。
在示例的第四个测试用例中,您可以将 $$$1$$$ 硬币添加到 $$$1$$$-st 箱子中,并将 $$$1$$$ 硬币添加到 $$$3$$$-rd 箱子中。