C. K-Complete Word
dfs and similar; dsu; greedy; implementation; strings
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.