长度为 $$$n$$$ 的单词 $$$s$$$ 被称为 $$$k$$$ 完成,如果
- $$$s$$$ 是回文,即 $$$s_i=s_{n+1-i}$$$ 对于所有 $$$1 \le i \le n$$$;
- $$$s$$$ 的周期为 $$$k$$$,即 $$$s_i=s_{k+i}$$$ 对于所有 $$$1 \le i \le n-k$$$。
例如,“abaaba”是一个 $$$3$$$ 完整的单词,而“abccba”则不是。
Bob 被给予一个长度为 $$$n$$$ 的单词 $$$s$$$,仅由小写拉丁字母和整数 $$$k$$$ 组成,这样 $$$n$$$ 可以被 $$$k$$$ 整除。他想将 $$$s$$$ 转换为任何 $$$k$$$ 完整单词。
为此,Bob 可以选择一些 $$$i$$$ ($$$1 \le i \le n$$$) 并将位置 $$$i$$$ 处的字母替换为其他小写拉丁字母。
所以现在 Bob 想知道他必须替换的最少字母数才能将 $$$s$$$ 转换为任何 $$$k$$$ 完整单词。
请注意,如果单词 $$$s$$$ 已经 $$$k$$$ 完成,则 Bob 可以进行零更改。
您需要独立回答 $$$t$$$ 测试用例。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t\le 10^5$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$, $$$n$$$ 可以被 $$$k$$$整除)。
每个测试用例的第二行包含长度为 $$$n$$$ 的单词 $$$s$$$。
保证单词 $$$s$$$ 仅包含小写拉丁字母。并且保证所有测试用例的$$$n$$$总和不会超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,表示将 $$$s$$$ 转换为任何 $$$k$$$ 完整单词时必须替换的最少字符数。
示例
输入 #1
4 6 2 abaaba 6 3 abaaba 36 9 hippopotomonstrosesquippedaliophobia 21 7 wudixiaoxingxingheclp
输出 #1
2 0 23 16
注意
在第一个测试用例中,一个最佳解决方案是 aaaaaa。
在第二个测试用例中,给定的单词本身是 $$$k$$$ 完整的。