Bookface

Taking on an ambitious project? Check. Working tirelessly, day and night, to deliver it before the deadline? Check. Committing your code every day in small chunks? Check. After all that work, you, the most ambitious software developer at Bookface to date, thought nothing stood between you and your promotion. You could not have been more wrong.

Before sending your promotion package to management, you asked your coworker Little Franiu to take a look. One quick look was enough to see the problem. "At Bookface, you have to move fast," said Franiu. "Move fast and change things. You can't be predictable and ship similarly sized commits every day like that!"

You looked at the number of lines you added on each of the $n$ days of the project, and saw that Franiu had a point. Let $c_i$ be this count for the $i$-th day. All the $c_i$ values are relatively close to each other. Franiu had an idea for fixing this: you can rewrite your commit history to make it look better.

Together with Franiu, you chose a value $d$ and decided that $|c_i - c_j| \ge d$ must hold for any $1 \le i < j \le n$. To that end, you can select a single day and either add or remove one line of code in the commit made on that day. You can perform arbitrarily many such operations, and each takes 1 second. How much time do you need to reach your goal? The number of lines in a commit must always stay non-negative.

The first line contains the number of test cases $z$ ($1 \le z \le 100000$). Each test case starts with a line containing $n$ and $d$ ($1 \le n \le 200000$, $1 \le d \le 10^6$). The next line contains $n$ integers $c_i$ ($0 \le c_i \le 3 \cdot 10^{11}$), the number of lines added on the $i$-th day. The total number of days over all test cases does not exceed $10^6$.

For each test case, output a single line containing one integer: the number of seconds needed to accomplish your goal.