리틀 $\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$입니다.