#include <bits/stdc++.h>
using namespace std;
const int inf = 1e5;
int a[200005][4];
int s[200005];
int main() {
  int q, n, k, x = 0, i, z;
  string st;
  cin >> q;
  for (; q > 0; q--) {
    cin >> n >> k;
    cin >> st;
    for (i = 0; i < n; i++) {
      if (st[i] == 'R') {
        s[i] = 0;
      } else if (st[i] == 'G') {
        s[i] = 1;
      } else
        s[i] = 2;
    }
    if (s[0] == 0) {
      a[0][1] = a[0][2] = 1;
      a[0][0] = 0;
    }
    if (s[0] == 1) {
      a[0][0] = a[0][2] = 1;
      a[0][1] = 0;
    }
    if (s[0] == 2) {
      a[0][1] = a[0][0] = 1;
      a[0][2] = 0;
    }
    for (i = 1; i < n; i++) {
      if (s[i] == 0) {
        a[i][0] = a[i - 1][2];
        a[i][1] = a[i - 1][0] + 1;
        a[i][2] = a[i - 1][1] + 1;
      } else if (s[i] == 1) {
        a[i][0] = a[i - 1][2] + 1;
        a[i][1] = a[i - 1][0];
        a[i][2] = a[i - 1][1] + 1;
      } else {
        a[i][0] = a[i - 1][2] + 1;
        a[i][1] = a[i - 1][0] + 1;
        a[i][2] = a[i - 1][1];
      }
    }
    x = 3 - k % 3;
    z = min(a[k - 1][0], min(a[k - 1][1], a[k - 1][2]));
    for (i = k; i < n; i++) {
      z = min(z, min(a[i][0] - a[i - k][(x) % 3],
                     min(a[i][1] - a[i - k][(x + 1) % 3],
                         a[i][2] - a[i - k][(x + 2) % 3])));
    }
    cout << z << endl;
  }
  return 0;
}
