数列をなめらかに

長さ $N$ の整数列 $A_1, A_2, \cdots, A_N$ が与えられる。

高々 $K$ 個の位置を選び、それぞれの位置の値を任意の整数に変更できる。変更後の数列を $B_1, B_2, \cdots, B_N$ とする。

$N \ge 2$ のとき、数列の 隣接差を次のように定義する。

$N=1$ のとき、隣接差は $0$ と定義する。

許された変更を行った後の隣接差の最小値を求めよ。

入力は標準入力から次の形式で与えられる。

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

各テストケースについて、可能な隣接差の最小値を 1 行に出力せよ。

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