Today is YQH's birthday, and she received a set of puzzle toys—$n$ electric towers—as a birthday gift. All electric towers are located on the same straight line. Specifically, if we represent the line as the non-negative half of a number line, the $i$-th electric tower is located at position $x_i$.

If the distance between two electric towers is strictly less than $d$, they will discharge electricity. After playing for a while, YQH gets bored and decides to pack up the towers. To avoid wasting electricity, she wants to adjust the towers so that none of them discharge.

Specifically, YQH can move any tower one unit in the positive or negative direction along the number line, provided that the tower remains on the non-negative half of the number line. You may assume that other towers do not interfere with the movement of a tower.

Moving towers is tiring, so YQH wants to find the minimum number of moves required to ensure that no towers discharge.

Input

The problem contains multiple test cases. The first line contains an integer $T$, representing the number of test cases.

For each test case:

The first line contains two positive integers $n$ and $d$.

The second line contains $n$ non-negative integers $x_i$, representing the positions of the towers.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

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

Output 1

6
16

For the first test case, consider the final positions of the towers $x^\prime=[0,1,2,3]$. It is clear that this satisfies the requirement that no towers discharge, and the number of moves is $\sum|x_i-x^\prime_i|=6$. It can be proven that there is no better solution.

For the second test case, consider the final positions of the towers $x^\prime=[0,100,20,10]$. The number of moves is $\sum|x_i-x^\prime_i|=16$. It can be proven that there is no better solution.

Input 2

See ex_ele2.in and ex_ele2.ans in the provided files.

Input 3

See ex_ele3.in and ex_ele3.ans in the provided files.

Constraints

For all data, it is guaranteed that $1\le T\le 10^5, 1\le n\le 2\times 10^5, 1\le d\le 10^6, 0\le x_i\le 3\times 10^{11}, \sum n\le 10^6$.

Subtask 1 (20 pts): $n\le 10, x_i\le 1000, T=1$.

Subtask 2 (20 pts): $d=1$.

Subtask 3 (10 pts): $n\le 200, T\le 5$.

Subtask 4 (20 pts): $n\le 2000, T\le 5$.

Subtask 5 (30 pts): No special restrictions.