你正在管理一列有 $n$ 节车厢的地铁列车。车厢里不均匀地分布着 $n \cdot k$ 个人；更具体地说，第 $i$ 节车厢里有 $h_i$ 个人。你想平衡载荷，使得每节车厢里恰好有 $k$ 个人。

在每个停靠站，一些人（可能没有）可以离开他们所在的车厢并奔跑前往另一节车厢，但他们在一次奔跑中移动的距离不能超过 $d$ 节车厢。

由你来决定谁在什么时候跑向哪里。你需要多少个停靠站才能达到目标？

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $d$ ($1 \le d \le n \le 10^6$)：车厢数量以及一个人一次最多可以奔跑的距离。

每个测试用例的第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($0 \le h_i \le 10^9$)：列车上人员的分布情况。$h_i$ 的总和可以被 $n$ 整除。

所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数：你需要的停靠站数量。

样例

输入格式 1

3
1 1
5
3 2
3 0 0
10 1
0 0 10 0 0 0 0 10 0 0

输出格式 1

0
1
2

说明

在第一个测试用例中，只有一节车厢，因此人数从一开始就是均匀分布的。

在第二个测试用例中，在开始之前，第一节车厢里有 3 个人：Aleksei、Dima 和 Kostya。在第一个停靠站，Dima 跑向第二节车厢，Kostya 跑向第三节车厢，因此只需一个停靠站即可使每节车厢都恰好有 1 个人。