该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

岐岐正在研究一种对字符串进行局部去重的操作。给定一个只包含小写字母的字符串，她希望通过对若干个位置的字符进行修改，使得任意相邻的 $K$ 个字符都互不相同。她想知道，最少需要多少次单字符替换操作才能达到这一目标。

题目描述

给定一个长度为 $N$ 的只含小写字母的字符串 $S$，你可以进行若干次操作：每次选择一个位置 $1 \le x \le N$ 和一个小写字母 $c$，将 $S_x$ 改为 $c$。使得操作结束后，字符串中每相邻 $K$ 个字符都两两不同。请你计算并输出达到这一要求的最少操作次数。保障 $1 \le K \le 13$。

输入格式

第一行一个整数 $T$，表示测试数据组数。
接下来 $T$ 组测试数据，每组包含两行：

• 第一行包含两个整数 $N, K$，分别表示字符串长度和子串的长度；
• 第二行包含一个长度为 $N$ 的字符串 $S$，只含小写字母。

输出格式

对于每组测试数据，输出一行一个整数，表示使得任意相邻 $K$ 个字符都不同所需的最少操作次数。

样例

5
6 3
abaaba
5 2
hooch
8 3
cherykid
9 3
abbabbaba
9 3
aabbaabba

2
1
0
3
4

样例解释

• 样例 1：初始字符串“abaaba”，$K=3$。可以将其修改为“abcabc”，共替换 2 次，此时任意相邻 3 个字符（“abc”、“bca”、“cab”、“abc”）都各不相同。
• 样例 3：字符串“cherykid”本身已经满足任意相邻 3 个字符互不相同，无需任何操作，答案为 0。

数据范围

• $1 \le T \le 10^5$
• $1 \le \sum N \le 10^6$
• $1 \le K \le 13$
• $S$ 中只含小写字母

附件