题目描述

Diana 喜欢最甜甜甜甜的小草莓，她有 $n$ 种类型的草莓，第 $i$ 种有 $a_i$ 颗。

Diana 想要用这些草莓制作成草莓礼盒，每个草莓礼盒里都有恰好 $k$ 颗类型互不相同的草莓。

一颗草莓只能放进至多一个草莓礼盒，当然也可以不放进礼盒留给 Diana 独自享用。

请求出最多能制作出多少个符合要求的草莓礼盒。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_{1\sim n}$。

输出格式

对于每组数据，输出一行一个整数表示答案。

4
3 1
1 1 1
3 10
1 2 3
2 2
5 6
5 3
6 9 4 2 1

3
0
5
6

数据范围

对于 $30\%$ 的数据，$n\leq 1000$，$k\leq 2$，$a_i\leq 10$。

对于 $60\%$ 的数据，$k\leq 2$。

对于 $100\%$ 的数据，$1\leq T\leq 100$，$1\leq n,k\leq 2\times 10^5$，$1\leq a_i\leq 10^9$，$\sum n\leq 2\times 10^5$。