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.

长度为 $n$ 的字符串 $s$ 被称为 $k$-完全的，当且仅当满足以下两个条件：

• $s$ 是一个回文串，即对所有 $1 \le i \le n$，均有 $s_i = s_{n+1-i}$；
• $s$ 具有周期 $k$，即对所有 $1 \le i \le n-k$，均有 $s_i = s_{k+i}$。

例如，"abaaba" 是一个 $3$-完全的字符串，而 "abccba" 则不是。

Bob 被给定一个长度为 $n$ 的字符串 $s$（仅由小写拉丁字母组成）以及一个整数 $k$，其中 $n$ 可被 $k$ 整除。他希望将 $s$ 转换为任意一个 $k$-完全的字符串。

为此，Bob 可以选择某个位置 $i$（$1 \le i \le n$），并将该位置上的字符替换为另一个小写拉丁字母。

现在 Bob 想知道：将 $s$ 转换为任意一个 $k$-完全字符串所需的最少字符替换次数是多少？

注意：若字符串 $s$ 本身已是 $k$-完全的，则 Bob 可以不进行任何修改（即替换次数为 $0$）。

你需要独立地回答 $t$ 组测试用例。

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 \lt 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$.

第一行包含一个整数 $t$（$1 \le t\le 10^5$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \lt n \le 2 \cdot 10^5$，且 $n$ 能被 $k$ 整除）。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$。

保证字符串 $s$ 仅由小写拉丁字母组成；且保证所有测试用例中 $n$ 的总和不超过 $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.

对于每个测试用例，输出一个整数，表示将 $s$ 转换为任意一个 $k$-完全单词所需替换的最少字符数。

In the first test case, one optimal solution is aaaaaa.

In the second test case, the given word itself is $k$-complete.

在第一个测试用例中，一个最优解是 aaaaaa。

在第二个测试用例中，给定的单词本身是 $k$-完备的。