在深入研究量子色动力学的复杂理论后，Little Cyan Fish 对“色荷”（color charge）的概念产生了浓厚的兴趣。为了测试你对该理论的理解，他向你提出了以下任务。

Little Cyan Fish 给你一个包含 $N$ 个顶点的图。每个顶点都被分配了一种颜色，颜色编号从 $1$ 到 $n$。被分配为颜色 $i$ 的顶点数量恰好为 $a_i$，使得顶点总数为 $\sum_{i=1}^{n} a_i = N$。最初，图中没有任何边。

你的任务是在满足特定约束的前提下，为该图添加边：任何两个相同颜色的顶点之间的距离必须大于或等于 $d$。此约束是为了避免相同颜色的顶点彼此靠得太近。值得注意的是，如果一对顶点之间没有路径，则它们的距离被视为无穷大。

你的目标是在遵守上述约束的同时，最大化图中边的数量。确定并输出在这些条件下可以添加到图中的最大边数。

输入格式

输入文件包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $d$ ($1 \le n \le 5 \times 10^5$, $1 \le d \le n$)。

下一行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$，对于所有 $1 \le i \le n$；$\sum_{i=1}^{n} a_i \le 10^9$)。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

输入 1

4
3 3
2 2 1
3 3
2 3 3
5 2
1 1 1 1 1
1 1
1

输出 1

4
7
10
0

说明

在第一个样例中，最多可以向图中添加 $4$ 条边。以下是一个可能的方案。