小 $\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$ 想要為旋律添上屬於自己嘅色彩：佢可以進行任意次修改，喺每次修改入面，佢都可以將樂譜入面某一個位置嘅音符改做任意正整數。經過若干次修改之後，原始樂譜 $b$ 變成咗小 $\omega$ 最終聽到嘅樂譜 $b'$。

小 $\omega$ 聽到咗呢段旋律 $b'$，並喺小 $\varepsilon$ 嘅夢囈入面得知咗數字 $k$。而家小 $\omega$ 想知道小 $\varepsilon$ 最少修改咗幾多個音符先至可以令原始樂譜 $b$ 變成自己最終聽到嘅 $b'$。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 10^4$），表示測試數據組數。

每組測試數據包含兩行：

• 第一行包含兩個整數 $n, k$（$2 \le k \le n \le 2 \times 10^5$），分別表示樂譜長度同樂句長度。
• 第二行包含 $n$ 個整數 $b'_1, b'_2, \dots, b'_n$（$1 \le b'_i \le 10^9$），表示小 $\omega$ 最終聽到嘅各個音符音高。

保證單個測試點入面所有數據 $n$ 嘅總和唔超過 $2 \times 10^5$。

輸出格式

對於每組測試數據，輸出一行一個非負整數，表示小 $\varepsilon$ 最少修改嘅音符數。

範例

範例輸入 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

範例解釋

對於第一組測試數據，可以取 $a = [2, 3, 1]$。呢個時候原始樂譜啱啱好係 $b = [2, 3, 1, 2, 3, 1]$，同最終嘅樂譜完全相同，所以小 $\varepsilon$ 冇修改任何音符。

對於第二組測試數據，可以取 $a = [1, 2, 3]$，得到 $b = [1, 2, 3, 1, 2]$。只需要將最後一個音符改做 $3$，就可以得到最終樂譜，所以答案係 $1$。

對於第三組測試數據，可以取 $a = [4, 1, 2, 3]$，得到 $b = [4, 1, 2, 3, 4]$。只需要將第 $2$ 個音符改做 $3$、第 $4$ 個音符改做 $1$，就可以得到最終樂譜，所以答案係 $2$。