小 $\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$。