Слово \(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\) независимых наборов входных данных.
Выходные данные
Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество позиций, буквы на которых ему придется заменить, чтобы превратить \(s\) в любое \(k\)-полное слово.
Примечание
В первом наборе входных данных одно из оптимальных решений — это «aaaaaa».
Во втором наборе входных данных слово уже \(k\)-полное.