题目描述

小杨拿到了一个长度为 $n$、只含小写字母的字符串 $s$。每次操作，他可以选一个位置 $x$（$1 \le x \le n$）和一个小写字母 $c$，把 $s_x$ 改为 $c$。

他需要进行若干次操作，使得操作结束后，字符串中任意相邻的 $k$ 个字符都互不相同（即任意长度为 $k$ 的连续子串中，$k$ 个字符两两不同）。

请你计算最少需要进行多少次操作。

输入格式

第一行一个整数 $t$，表示测试数据组数。

接下来 $t$ 组测试数据，对于每组：

• 第一行两个整数 $n, k$，分别表示字符串长度和窗口长度；
• 第二行一个长度为 $n$ 的字符串 $s$，只含小写字母。

输出格式

对于每组测试数据，输出一行一个整数，表示最少的操作次数。

样例

3
6 3
abaaba
5 2
hooch
8 3
cherykid

2
1
0

样例解释

第一组中，abaaba 的第 $3$、$6$ 个字符 a 都与前面 $k-1=2$ 个字符中的某个重复，分别改成 c 后得到 abcabc，此后任意相邻 $3$ 个字符都互不相同，共 $2$ 次操作。

第二组中，$k=2$，hooch 里两个相邻的 o 重复，改掉其中一个即可，需要 $1$ 次操作。

第三组中，cherykid 已经满足任意相邻 $3$ 个字符互不相同，不需要操作。

数据范围与约定

对于 $100\%$ 的数据，$1 \le t \le 10^5$，$\sum n \le 10^6$，$1 \le k \le 13$，$s$ 中只含小写字母。