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

文件输入输出提示

本题采用文件输入输出。提交代码时，请在 main 函数开头加入文件重定向，并从 ring.in 读入、输出到 ring.out。

freopen("ring.in", "r", stdin);
freopen("ring.out", "w", stdout);

题目描述

苗苗正在布置活动室门口的环形灯带。灯带由 $n$ 盏灯组成，每盏灯的颜色是 R、G、B 中的一种。

苗苗要从灯带中选择连续的 $k$ 盏灯作为欢迎区域。灯带是环形的，所以可以从最后一盏灯继续数到第一盏灯。

欢迎区域的颜色需要变成下面三种循环模式之一：

• RGBRGB...
• GBRGBR...
• BRGBRG...

如果欢迎区域还不符合要求，可以进行重涂。每次操作可以把一盏灯重涂成任意一种颜色。

请你求出，最少需要重涂多少盏灯，才能让某个长度为 $k$ 的连续区域满足要求。

输入格式

从文件 ring.in 中读入数据。

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行输入两个整数 $n,k$。

第二行输入一个长度为 $n$ 的字符串 $s$，表示从某个位置开始顺时针记录的灯带颜色。

输出格式

输出到文件 ring.out 中。

对于每组测试数据，输出一行一个整数，表示最少需要重涂的灯数。

输入输出样例 #1

输入 #1

3
5 3
RGRBR
6 4
RRRRRR
4 4
BRGB

输出 #1

1
2
0

说明/提示

第一组数据中，选择第 1 到第 3 盏灯，颜色为 RGR，只需把第 3 盏灯重涂为 B，即可变成循环模式 RGB。

第二组数据中，任意选择 4 盏连续的灯，至少需要重涂 2 盏。

第三组数据中，选择从第 1 盏灯开始的 4 盏灯，颜色为 BRGB，已经符合循环模式。

输入输出样例 #2

输入 #2

2
6 4
BRBBRG
8 5
BBBBBBBB

输出 #2

0
3

第二个样例中，第一组数据可以选择第 5、第 6、第 1、第 2 盏灯，颜色依次为 RGBR，不需要重涂。第二组数据中，所有灯都是 B，长度为 5 的区域至少需要重涂 3 盏灯。

数据范围与子任务

对于所有数据，满足：

• $1\le T\le 10^5$；
• $1\le k\le n$；
• $s$ 仅由字符 R、G、B 组成；
• 所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

ring_大样例.zip