← 返回题目列表

Codeforces · 1966/A

A. 换卡

中文机器翻译题面 查看原题

你有一手$$$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$$$牌。