Problem Description

有 $n$ 个选手参加了 2050 编程竞赛，他们属于 $m$ 个学校，学校的编号为 $1$ 到 $m$，2050 编程竞赛的 PASS 奖励资格如下：对于一个学校，如果它有 $x$ 个学生参赛，它的参赛学生里成绩最好的 $\lfloor \frac{x}{k} \rfloor$ 人里，每有一个人总排名在前 $50\%$ 内（包括$50\%$），就奖励一个 PASS。

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

Input

第一行一个正整数 $T~(1\leq T\leq 10)$ 表示数据组数。

接下来 $T$ 组数据，对于每组数据：

第一行三个正整数 $n,m,k~(1\leq n\leq 10^4,1\leq m\leq 10^3,2\leq k\leq 20)$。

第二行 $n$ 个数，按照成绩从好到差给出 $n$ 个选手所属的学校。

Output

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

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

2
2