1332C. C. K-Complete Word

CF1332C. K-Complete Word

时限: 2 秒 | 内存: 512 MB | 输入: 标准输入 | 输出: 标准输出

长度为 $n$ 的单词 $s$ 被称为 $k$-完全（$k$-complete），如果满足以下两个条件：

• $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$-完全的，则可以不进行任何操作。

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

输入格式

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

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

每组测试用例的第二行包含一个长度为 $n$ 的单词 $s$。

保证单词 $s$ 只包含小写拉丁字母。并且保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

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

样例输入 1

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

样例输出 1

2
0
23
16

提示

在第一个测试用例中，一种最优方案是将所有字母都变为 a，得到 "aaaaaa"。

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