正在进行一个雄心勃勃的项目？确认。没日没夜地工作，只为在截止日期前交付？确认。每天分批提交代码？确认。在完成所有这些工作后，作为 Bookface 迄今为止最有抱负的软件开发人员，你认为晋升之路已无阻碍。但你大错特错了。

在将晋升材料提交给管理层之前，你决定请同事小 Franiu 帮忙看一看。他只看了一眼就发现了问题。“在 Bookface，你必须行动迅速，”Franiu 说，“要快速行动，不断改变。你不能总是循规蹈矩，每天提交规模相似的代码！”

你查看了项目 $n$ 天中每一天提交的代码行数，意识到 Franiu 说得有道理。如果我们将第 $i$ 天的提交行数记为 $c_i$，那么所有的 $c_i$ 值都非常接近。幸运的是，你的朋友想到了一个补救办法——你可以重写提交历史，让它看起来更好！

你和 Franiu 选择了一个值 $d$，并决定要求对于任意 $1 \le i < j \le n$，都满足 $|c_i - c_j| \ge d$。为此，你可以选择某一天，对该天的提交增加或减少一行代码。你可以执行任意多次此类操作，每次操作耗时 1 秒。你需要多少时间才能达成目标？当然，每一天提交的代码行数必须始终保持为非负数。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 100\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含项目天数 $n$ ($1 \le n \le 200\,000$) 和选定的常数 $d$ ($1 \le d \le 10^6$)。第二行包含 $n$ 个整数 $c_i$ ($0 \le c_i \le 3 \cdot 10^{11}$)，表示第 $i$ 天提交的代码行数。

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

输出格式

对于每个测试用例，输出一行，包含一个整数，即达成目标所需的时间（秒数）。

样例

样例输入 1

2
4 1
0 0 0 0
4 10
1 100 5 10

样例输出 1

6
16