1007. G. Perfect Palindrome

题目描述

给定一个长度为 (n) 的小写字母字符串 (A)，以及一个非负整数 (d)。

定义 (f(A, x)) 表示将字符串 (A) 循环左移 (x) 位后得到的字符串。例如，若 (A = \texttt{"abcde"})，(f(A, 2) = \texttt{"cdeab"})。

如果对于所有非负整数 (k \ge 0)，字符串 (f(A, kd)) 都是回文串，则称 (A) 是一个 (d)-完美回文串。

回文串是指正着读和反着读都一样的字符串。

现在你可以进行若干次操作，每次操作将 $A$ 中的一个字符修改为任意一个小写英文字母。求将 $A$ 变为 $d$-完美回文串所需的最少操作次数。

样例解释

对于样例字符串 abcaabda，要满足题意，需要让所有会互相对应的位置字符一致。

其中一组对应位置上的字符已经都是 a，不需要修改；另一组对应位置上的字符是 b, c, b, d，可以保留两个 b，把 c 和 d 改成 b。

这样总共修改 2 次，得到例如 abbaabba 的合法字符串，因此答案是 2。

数据范围

• (1 \le T \le 10)
• (1 \le n \le 10^5)
• (0 \le d < n)
• 字符串 (A) 仅包含小写字母。
• 所有测试数据的 (n) 之和不超过 (2\times10^5)。

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)（(1 \le T \le 10)），表示测试数据组数。

对于每组测试数据： 第一行包含两个整数 (n, d)（(1 \le n \le 10^5, 0 \le d < n)）。 第二行包含一个长度为 (n) 的小写字母字符串 (A)。

输出格式

对于每组数据，输出一个整数，表示最少修改次数。

样例输入

1
8 2
abcaabda

样例输出

2

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1007