북페이스

야심 찬 프로젝트를 맡았는가? 확인. 마감 전에 끝내려고 밤낮없이 쉬지 않고 일하는가? 확인. 코드를 매일 작은 단위로 나누어 커밋하는가? 확인. 이 모든 노력 끝에 Bookface에서 지금까지 가장 야심 찬 소프트웨어 개발자인 당신은 승진을 막을 것이 아무것도 없다고 생각했다. 하지만 크게 틀렸다.

승진 서류를 경영진에게 보내기 전에, 동료 Little Franiu에게 한번 봐 달라고 부탁했다. 한눈에 문제가 보였다. Franiu가 말했다. "Bookface에서는 빨리 움직여야 해요. 빠르게 움직이고 이것저것 바꿔야죠. 매일 비슷한 크기의 커밋을 올리면 예측 가능해지잖아요!"

프로젝트의 $n$일 동안 매일 추가한 줄 수를 살펴보니 Franiu의 말에 일리가 있었다. $i$일째의 줄 수를 $c_i$라고 하자. 모든 $c_i$ 값이 서로 비슷하게 가까웠다. 다행히 Franiu가 해결 방법을 알려 주었다. 커밋 기록을 고쳐 쓰면 된다는 것이다.

Franiu와 함께 값 $d$를 정하고, 임의의 $1 \le i < j \le n$에 대해 $|c_i - c_j| \ge d$가 성립하도록 하기로 했다. 이를 위해 하루를 골라 그날 커밋의 코드 줄을 한 줄 추가하거나 한 줄 삭제할 수 있다. 이 연산은 원하는 만큼 몇 번이든 할 수 있고, 한 번에 1초가 걸린다. 목표를 달성하는 데 몇 초가 필요한가? 커밋의 줄 수는 항상 0 이상이어야 한다.

첫 줄에 테스트 케이스의 개수 $z$($1 \le z \le 100000$)가 주어진다. 각 테스트 케이스는 $n$과 $d$가 적힌 줄로 시작한다($1 \le n \le 200000$, $1 \le d \le 10^6$). 다음 줄에는 $n$개의 정수 $c_i$($0 \le c_i \le 3 \cdot 10^{11}$)가 주어지며, 이는 $i$일째에 추가한 줄 수이다. 모든 테스트 케이스의 총 일수는 $10^6$을 넘지 않는다.

각 테스트 케이스마다 목표를 달성하는 데 필요한 초를 나타내는 정수 하나를 한 줄에 출력한다.