#719 Smoothing a Sequence

Statement

Statement language

An integer sequence $A_1, A_2, \cdots, A_N$ of length $N$ is given.

You may choose at most $K$ positions and replace the value at each chosen position with any integer. Let the resulting sequence be $B_1, B_2, \cdots, B_N$ .

For $N \ge 2$ , define the adjacent difference of the sequence as

\max_{1 \le i < N} |B_i-B_{i+1}|.

For $N=1$ , the adjacent difference is defined to be $0$ .

Find the minimum possible adjacent difference after the allowed replacements.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum possible adjacent difference on one line.

Constraints

$1 \le T \le 200\,000$ .
$1 \le N \le 200\,000$ .
$0 \leq K$ .

Subtasks

#	Score	Constraints
1	8	$N \le 12$ . The sum of $N$ over all test cases does not exceed $200$ .
2	14	$K=0$ .

Samples

Input

Output