K-Complete Word

题意翻译

- 给定一个长度为 $n$ 的字符串 $s$ 和一个参数 $k$，保证 $k$ 整除 $n$ 并且 $s$ 中只含小写字母。 - 请修改 $s$ 中一些字符，使得修改后的字符串满足是以 $k$ 为循环节长度的回文串。 - 以 $k$ 为循环节指对于所有的 $1 \leq i \leq n - k$，$s_i = s_{i + k}$。 - 求最少的修改次数。 - 多组数据，$n$ 之和不超过 $2 \times 10^5$，$k < n$。

题目描述

Word $ s $ of length $ n $ is called $ k $ -complete if - $ s $ is a palindrome, i.e. $ s_i=s_{n+1-i} $ for all $ 1 \le i \le n $ ; - $ s $ has a period of $ k $ , i.e. $ s_i=s_{k+i} $ for all $ 1 \le i \le n-k $ . For example, "abaaba" is a $ 3 $ -complete word, while "abccba" is not. Bob is given a word $ s $ of length $ n $ consisting of only lowercase Latin letters and an integer $ k $ , such that $ n $ is divisible by $ k $ . He wants to convert $ s $ to any $ k $ -complete word. To do this Bob can choose some $ i $ ( $ 1 \le i \le n $ ) and replace the letter at position $ i $ with some other lowercase Latin letter. So now Bob wants to know the minimum number of letters he has to replace to convert $ s $ to any $ k $ -complete word. Note that Bob can do zero changes if the word $ s $ is already $ k $ -complete. You are required to answer $ t $ test cases independently.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t\le 10^5 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le k < n \le 2 \cdot 10^5 $ , $ n $ is divisible by $ k $ ). The second line of each test case contains a word $ s $ of length $ n $ . It is guaranteed that word $ s $ only contains lowercase Latin letters. And it is guaranteed that the sum of $ n $ over all test cases will not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output one integer, representing the minimum number of characters he has to replace to convert $ s $ to any $ k $ -complete word.

输入输出样例

输入样例 #1

4
6 2
abaaba
6 3
abaaba
36 9
hippopotomonstrosesquippedaliophobia
21 7
wudixiaoxingxingheclp

输出样例 #1

2
0
23
16

说明

In the first test case, one optimal solution is aaaaaa. In the second test case, the given word itself is $ k $ -complete.