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

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

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

请求出最多能制作出多少个符合要求的草莓礼盒。 输入格式 第一行一个整数 T T 表示数据组数。

对于每组数据：

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

第二行 n n 个整数 a 1 ∼ n a 1∼n ​ 。

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

数据范围对于 30% 的数据， 1000 n≤1000， k≤2， a i ​ ≤10。

对于 60% 的数据， k≤2。

对于 100% 的数据， 1≤T≤100， 1≤n,k≤2×10 1≤a i ​ ≤10 9 ， ∑ n ≤ 2 × 1 0 5 。

样例数据 输入: 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