In an alternate universe, you are the Earth god tasked with the responsibility of managing terrain safety. Your most pressing duty is that of $N$ hills lined up in a single row. You know that the $i^{th}$ hill from the left currently has height $H_i$. In your world, the danger factor of any terrain is the maximum difference in height between any $2$ adjacent hills. Formally, the danger factor is defined as $\underset{1\le i\le N-1}{max}(|H_i-H_{i+1}|)$. To minimize the danger factor, you are allowed to change the height of at most $K$ hills, each to any positive integer of your choosing (the resulting height may be different for each hill). Please find the minimum possible danger factor after doing so. To ensure the integrity of your solution, there may be multiple test cases.

Constraints

For this problem, you will NOT be required to pass the sample case in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

$1\le T\le 500$

$2\le N\le 2\times {10}^5$

$0\le K\le N$

$1\le H_i\le {10}^9$

The sum of $N$ over all test cases will not exceed $2\times {10}^5$.

Subtask 1 [5%]

$K=0$

Subtask 2 [5%]

$K=1$

Subtask 3 [10%]

$K=2$

Subtask 4 [80%]

No additional constraints.

Input Specification

The first line contains an integer $T$, the number of test cases. The next $2T$ lines will describe the test cases.

The first line of each test case contains $2$ integers $N$ and $K$, the number of hills and the number of hills whose height you may change.

The second line of each test case contains $N$ integers $H_i$ $(1\le i\le N)$, the height of the $i^{th}$ hill from the left.

Output Specification

For each test case output one integer on its own line, the minimum possible danger factor after changing the height of at most $K$ hills.

Sample Input

2
6 2
1 3 7 2 3 6
7 4
1 5 8 5 5 7 8

Sample Output

2
0

Explanation

For the first test case, one possible solution is to change the height of the third hill to $4$ and the height of the sixth hill to $1$, as depicted in the diagram above. The resulting danger factor is $max(|1-3|,|3-4|,|4-2|,|2-3|,|3-1|)=2$.

For the second test case, the optimal solution is to change the heights of the first, third, sixth, and seventh hills all to $5$. Since all hills have the same height now, the resulting danger factor is $0$.