有一天,沃贡斯想要通过一个拥有 $$$n$$$ 行星的遥远系统建造一条新的超空间高速公路。第 $$$i$$$ 行星位于 $$$a_i$$$ 轨道上,同一轨道上可能有多个行星。可惜所有的星球都在路上,需要毁灭。
Vogons 有两台机器可以做到这一点。
- 一次操作中的第一台机器可以摧毁任何行星,成本为 $$$1$$$ Triganic Pu。
- 一次操作中的第二台机器可以摧毁该系统中单个轨道上的所有行星,代价是 $$$c$$$ Triganic Pus。
沃贡人可以根据需要多次使用每台机器。
沃贡人非常贪婪,所以他们想用最少的钱摧毁所有的星球。你能帮助他们了解这个项目的最低成本吗?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是测试用例。
每个测试用例由两行组成。
第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$1 \le n, c \le 100$$$) — 行星数量和第二台机器使用的成本。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 行星的轨道。
输出
对于每个测试用例,打印一个整数 - 摧毁所有行星的最低成本。
示例
输入 #1
4 10 1 2 1 4 5 2 4 5 5 1 2 5 2 3 2 1 2 2 2 2 1 1 2 2 1 2
输出 #1
4 4 2 2
输入 #2
1 1 100 1
输出 #2
1
注意
在第一个测试用例中,使用两台机器的成本是相同的,因此您始终可以使用第二台机器并摧毁轨道上的所有行星 $$$1$$$、轨道上的所有行星 $$$2$$$、轨道上的所有行星 $$$4$$$、轨道上的所有行星 $$$5$$$。
在第二个测试用例中,使用第二台机器进行 $$$2$$$ Triganic Pus 摧毁 $$$2$$$ 轨道上的所有行星,然后使用第一台机器摧毁剩余的两颗行星是有利的。
在第三个测试用例中,您可以使用第一台机器两次或第二台机器一次。
在第四个测试用例中,使用第一台机器两次是有利的。