有 nn 个选手参加了 2050 编程竞赛，他们属于 mm 个学校，学校的编号为 11 到 mm，2050 编程竞赛的 PASS 奖励资格如下：对于一个学校，如果它有 xx 个学生参赛，它的参赛学生里成绩最好的 ⌊xk⌋⌊xk⌋ 人里，每有一个人总排名在前 50%50% 内（包括50%50%），就奖励一个 PASS。

现在给出每个选手所属的学校和它的排名（假设没有平手），请你帮主办方算一下一共发出了几个 PASS。

Input第一行一个正整数 T (1≤T≤10)T (1≤T≤10) 表示数据组数。

接下来 TT 组数据，对于每组数据：

第一行三个正整数 n,m,k (1≤n≤104,1≤m≤103,2≤k≤20)n,m,k (1≤n≤104,1≤m≤103,2≤k≤20)。

第二行 nn 个数，按照成绩从好到差给出 nn 个选手所属的学校。Output对于每组数据输出一行一个整数表示答案。Sample Input

2
6 2 2 
1 1 2 1 2 2 
8 2 2
1 1 2 1 2 2 2 2

Sample Output

2
2

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;

#define ll long long

int t, n, m, k, school[1000+8], sum, man[10000+8], grade[10000+8];

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        sum = 0;
        memset(school, 0, sizeof(school));
        memset(grade, 0, sizeof(grade));
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &man[i]);
            school[man[i]]++;
            grade[i] = school[man[i]];
        }
        for(int i = 1; i <= n; i++)
        {
//            cout<<i<<"    "<<"school/k sum: "<<school[man[i]]/k<<"    n/2: "<<n/2<<endl;
            if(grade[i] <= school[man[i]]/k && i <= n/2)sum++;
        }
        printf("%d\n", sum);
    }
    return 0;
}