B. Balanced Tournament
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Each year, Hogwarts organizes a tournament between different schools to win the Winter Cup. There are $$$N$$$ participating schools. Each school is represented by a champion. Each champion is selected by the Goblet of Fire, a magical object tasked with the selection. The $$$i^{th}$$$ champion has power $$$P_{i}$$$. Dumbledore wants to make this year's edition even more exciting so he introduced two new potions. The first potion increases the power of the wizard by $$$K$$$ while the second potion decreases it by $$$K$$$. Dumbledore will give each wizard at most one potion. He wants to minimize the difference of power between the strongest and the weakest wizard.

Help Dumbledore balance the tournament.

Input

The first line contains an integer $$$T$$$ $$$(1 \le T \le 500)$$$ denoting the number of testcases.

The first line of each testcase in the input contains two integers $$$N$$$ $$$(1 \le N \le 10^3)$$$ and $$$K$$$ $$$(0 \le K \le 10^9).$$$

The second line contains $$$N$$$ integers $$$P_{1},\dots,P_N$$$ $$$(1 \le P_{i} \le 10^{9})$$$ representing the original power of each wizard.

It is guaranteed that the sum of $$$N$$$ across all test cases doesn't exceed $$$5\times 10^{3}$$$

Output

Print the smallest possible difference of power.

Example
Input
3
5 1
1 2 3 4 5
4 2
1 3 5 9
4 5
1 2 3 4
Output
2
4
3