CF1332C K-Complete Word

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.

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