你有一手$$$n$$$牌,每张牌上都写有一个数字,以及一个固定整数$$$k$$$。您可以多次执行以下操作:
- 从你的手上选择任何具有相同数字的 $$$k$$$ 卡。
- 将这些卡牌兑换为$$$k-1$$$卡牌,每张卡牌可以有您选择的任意号码(包括您刚刚交换的卡牌上写的号码)。
这是第一个示例情况的一个可能的操作序列,其中 $$$k=3$$$:
在此过程结束时,您手上至少可以拥有多少张牌?
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$, $$$2 \le k \le 100$$$) - 分别是你拥有的牌的数量,以及你在每次操作中交换的牌的数量。
每个测试用例的下一行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots c_n$$$ ($$$1 \le c_i \le 100$$$) - 写在卡片上的数字。
输出
对于每个测试用例,输出一个整数 - 在进行任意次数的操作后,您手上剩余的牌的最小数量。
示例
输入 #1
7 5 3 4 1 1 4 4 1 10 7 7 2 4 2 1 100 5 2 3 10 4 1 1 1 1 1 1 1 1 1 1 5 2 3 8 1 48 7 6 2 10 20 30 10 20 40 6 3 10 20 30 10 20 40
输出 #1
2 1 1 3 5 1 6
注意
第一个示例对应于上图。那里显示的操作顺序是最佳的,所以答案是$$$2$$$。
在第二个示例中,无法执行任何操作,因此答案为 $$$1$$$。
在第四个示例中,您可以重复选择编号为$$$1$$$的$$$4$$$牌,并将其替换为编号为$$$1$$$的$$$3$$$牌,直到剩下$$$3$$$牌。