C. K-полное слово
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Слово $$$s$$$ длины $$$n$$$ называется $$$k$$$-полным, если

  • $$$s$$$ — палиндром, то есть $$$s_i=s_{n+1-i}$$$ для всех $$$1 \le i \le n$$$;
  • $$$s$$$ имеет период $$$k$$$, то есть $$$s_i=s_{k+i}$$$ для всех $$$1 \le i \le n-k$$$.

Например, «abaaba» — это $$$3$$$-полное слово, а «abccba» нет.

Бобу вручили слово $$$s$$$ длины $$$n$$$, состоящее только из строчных букв латинского алфавита, и целое число $$$k$$$ такое, что $$$n$$$ делится на $$$k$$$. Он хочет превратить слово $$$s$$$ в любое $$$k$$$-полное слово.

Для этого Боб может выбирать некоторую позицию $$$i$$$ ($$$1 \le i \le n$$$) и заменять букву на позиции $$$i$$$ на любую другую строчную букву латинского алфавита.

Поэтому теперь Боба интересует минимальное количество позиций, буквы на которых ему необходимо заменить, чтобы превратить $$$s$$$ в любое $$$k$$$-полное слово.

Обратите внимание, что Боб может сделать ноль изменений, если слово $$$s$$$ уже $$$k$$$-полное.

Требуется ответить на $$$t$$$ независимых наборов входных данных.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t\le 10^5$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$, $$$n$$$ делится на $$$k$$$).

Во второй строке записано слово $$$s$$$ длины $$$n$$$.

Гарантируется, что слово $$$s$$$ состоит только из строчных букв латинского алфавита. Также гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество позиций, буквы на которых ему придется заменить, чтобы превратить $$$s$$$ в любое $$$k$$$-полное слово.

Пример
Входные данные
4
6 2
abaaba
6 3
abaaba
36 9
hippopotomonstrosesquippedaliophobia
21 7
wudixiaoxingxingheclp
Выходные данные
2
0
23
16
Примечание

В первом наборе входных данных одно из оптимальных решений — это «aaaaaa».

Во втором наборе входных данных слово уже $$$k$$$-полное.