卡雷尔是一家汽车经销店的推销员。经销商有 $$$n$$$ 不同型号的汽车。第 $$$i$$$ 型号有 $$$a_i$$$ 辆车。卡雷尔是一位出色的销售人员,可以说服客户购买最多 $$$x$$$ 的汽车(卡雷尔选择的),只要这些汽车来自不同型号。
确定卡雷尔出售所有汽车所需引入的最低客户数量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 5 \cdot 10^5$$$; $$$1 \le x \le 10$$$) - 不同型号汽车的数量以及 Karel 可以说服客户购买的最大汽车数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 每个型号的汽车数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出销售所有汽车所需的最小可能客户数量。
示例
输入 #1
4 3 2 3 1 2 3 3 2 1 3 5 3 2 2 1 9 2 7 4 2 5 3 3 5 2 5
输出 #1
3 3 9 7
注意
对于第一种情况,Karel 只需要吸引 $$$3$$$ 客户。他将说服顾客购买以下型号的汽车:
- 客户 $$$1$$$ 购买型号为 $$$1$$$ 和 $$$3$$$ 的 $$$2$$$ 汽车。
- 客户 $$$2$$$ 购买型号为 $$$1$$$ 和 $$$2$$$ 的 $$$2$$$ 汽车。
- 客户 $$$3$$$ 购买型号为 $$$1$$$ 和 $$$3$$$ 的 $$$2$$$ 汽车。
对于第二种情况,Karel 只需要吸引 $$$3$$$ 客户。他将说服顾客购买以下型号的汽车:
- 客户 $$$1$$$ 购买型号为 $$$1$$$ 和 $$$3$$$ 的 $$$2$$$ 汽车。
- 客户 $$$2$$$ 购买型号为 $$$1$$$、$$$2$$$ 和 $$$3$$$ 的 $$$3$$$ 汽车。
- 客户 $$$3$$$ 购买了 $$$1$$$ 汽车,型号为 $$$3$$$。