RGB Substring (hard version)

/**
 *    author: Akvicor
 *    created: 2019-07-25 00-14-18
**/

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
#define FAST_IO 17
#else
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define per(i, a, n) for(int i = a; i >= (n); --i)
#define peer(i, a, n) for(int i = a; i > (n); --i)
#define prec(x) fixed << setprecision(x)
#define ms(s, n) memset(s, n, sizeof(s))
#define all(v) (v).begin(), (v).end()
#define sz(x) ((int)(x).size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define fi first
#define se second
#define MOD(x) const int MOD = (int)x
#define MAXN(x) const int MAXN = (int)x + 10

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;

namespace SOL{

const double EPS = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL LINF = 0x7f7f7f7f7f7f7f7f;

/**  >------- Akvicor's Solution -------< **/

MOD(1e9+7);
MAXN(1e6);

int q, n, k;
int ans;

void Find(string t, string &s){
	int l = 0, r = 0, res = 0;
	while(l <= n){
		while(r <= n && r-l < k){
			res += (s[r]==t[r%3]); // 记录有多少位匹配
			++r;
		}
		if(r-l < k) break;
		ans = max(ans, res);
		res -= (s[l]==t[l%3]); // 开头右移一位
		++l;
	}
}

void solve(){
    FAST_IO;
    
    cin >> q;
	while(q-- > 0){
		ans = 0;
		string s;
		cin >> n >> k >> s;
		Find("RGB", s);
		Find("GBR", s);
		Find("BRG", s);
		cout << (k-ans) << endl;
	}
    
}

/**  >----------------------------------< **/

}

int main(){

#ifdef DEBUG
    int DEBUGCNT = 0;
    clock_t DEBUGstart, DEBUGfinish;
    double DEBUGduration;
    cout << endl << ">------- Akvicor's Solution -------<" << endl << endl;
    while (DEBUGCNT < 70) {
        cout << ">---> Test: #" << DEBUGCNT << " <---<" << endl;
        DEBUGstart = clock();
#endif

        SOL::solve();

#ifdef DEBUG
        DEBUGfinish = clock();
        DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
        cout << ">---> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <---<" << endl << endl;
        if (cin.eof()) break;
        if (!cin.good()) break;
        if (cin.fail()) break;
        if (cin.bad()) break;
        ++DEBUGCNT;
    }
    cout << ">----------------------------------<" << endl << endl;
#endif

    return 0;
}