题目描述

Charles 将一个字符串的好分数定义为满足 $S_i \ne S_{N-i+1}$ 的下标 $i$ 的个数，其中 $1 \le i \le N/2$（下标从 $1$ 开始）。例如，字符串 CABABC 的好分数为 $2$，因为 $S_2 \ne S_5$ 且 $S_3 \ne S_4$。

Charles 给了 Ada 一个长度为 $N$ 的字符串 $S$（由大写字母组成），并要求她将其转换为一个好分数恰好为 $K$ 的字符串。在一次操作中，Ada 可以将字符串中的任意一个字符更改为任意大写字母。你能帮助 Ada 求出将给定字符串转换为好分数等于 $K$ 的字符串所需的最少操作次数吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $K$。第二行包含一个长度为 $N$ 的字符串 $S$，由大写字母组成。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是将给定字符串 $S$ 转换为好分数等于 $K$ 的字符串所需的最少操作次数。

2
5 1
ABCAA
4 2
ABAA

Case #1: 0
Case #2: 1

提示

在样例 #1 中，给定字符串已经具有好分数 $1$。因此所需的最少操作次数为 $0$。

在样例 #2 中，一种方案是将下标 $1$ 的字符改为 B，从而获得好分数 $2$。因此所需的最少操作次数为 $1$。

限制条件

$1 \le T \le 100$。

$0 \le K \le N/2$。

测试集 1

$1 \le N \le 100$。

测试集 2

最多 $10$ 个测试用例满足 $1 \le N \le 2 \times 10^5$。

其余测试用例满足 $1 \le N \le 100$。

翻译由 DeepSeek V4 Pro 完成