小 $\varepsilon$ と小 $\omega$ は音楽を愛する二人の女の子です。二人だけの思い出を記念して、小 $\varepsilon$ は小 $\omega$ のためにある旋律を書き下ろしました。

小 $\varepsilon$ は楽章の中の各音符をその音高に応じて整数として記録しました。彼女は長さ $k$ のある楽句 $a$ を選びました。ここで $a$ は列 $[1, 2, \dots, k]$ のある巡回シフトであり、すなわち非負整数 $p$（$0 \le p < k$）が存在して $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$ となります。次に、彼女はこの楽句を何度も繰り返し、先頭の $n$ 個の音符を取り出すことで元の楽譜 $b$ を得ました。

例えば、$k = 4$ のとき、$a$ は $[1, 2, 3, 4]$、$[2, 3, 4, 1]$、$[3, 4, 1, 2]$、または $[4, 1, 2, 3]$ のいずれかになり得ます。もし $a = [2, 3, 4, 1]$ かつ $n = 10$ であれば、$b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$ となります。

旋律を小 $\omega$ に贈る前に、小 $\varepsilon$ は旋律に自分ならではの彩りを添えたいと考えました。彼女は任意の回数だけ変更を行うことができ、各変更において楽譜のある 1 つの位置の音符を任意の正の整数に書き換えることができます。何回かの変更を経た後、元の楽譜 $b$ は小 $\omega$ が最終的に聴いた楽譜 $b'$ になりました。

小 $\omega$ はこの旋律 $b'$ を聴き、また小 $\varepsilon$ の寝言から数 $k$ を知りました。今、小 $\omega$ は小 $\varepsilon$ が元の楽譜 $b$ を自分が最終的に聴いた $b'$ にするために最小で何個の音符を変更したかを知りたいと思っています。

入力

1 行目にはテストケースの数を表す整数 $T$（$1 \le T \le 10^4$）が与えられます。

各テストケースは 2 行からなります：

• 1 行目には楽譜の長さと楽句の長さをそれぞれ表す 2 つの整数 $n, k$（$2 \le k \le n \le 2 \times 10^5$）が与えられます。
• 2 行目には $n$ 個の整数 $b'_1, b'_2, \dots, b'_n$（$1 \le b'_i \le 10^9$）が与えられ、小 $\omega$ が最終的に聴いた各音符の音高を表します。

1 つのテストファイル内のすべてのテストケースにおける $n$ の総和は $2 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、小 $\varepsilon$ が変更した音符の最小個数を表す非負整数を 1 行に出力してください。

入出力例

入力 1

8
6 3
2 3 1 2 3 1
5 3
1 2 3 1 3
5 4
4 3 2 1 4
6 3
1 3 1 3 1 3
5 2
1 1 1 1 1
6 4
1 2 3 4 5 6
6 2
172 723 593 904 219 576
5 3
3 1 1000000000 999999999 1

出力 1

0
1
2
4
2
2
6
2

注記

1 番目のテストケースでは、$a = [2, 3, 1]$ と選ぶことができます。このとき元の楽譜はちょうど $b = [2, 3, 1, 2, 3, 1]$ となり、最終的な楽譜と完全に一致するため、小 $\varepsilon$ は音符を 1 つも変更していません。

2 番目のテストケースでは、$a = [1, 2, 3]$ と選ぶことで、$b = [1, 2, 3, 1, 2]$ が得られます。最後の音符だけを $3$ に変更すれば最終的な楽譜が得られるため、答えは $1$ です。

3 番目のテストケースでは、$a = [4, 1, 2, 3]$ と選ぶことで、$b = [4, 1, 2, 3, 4]$ が得られます。$2$ 番目の音符を $3$ に、$4$ 番目の音符を $1$ に変更するだけで最終的な楽譜が得られるため、答えは $2$ です。