#include <bits/stdc++.h>
using namespace std;
const long double PI = acos((long double)-1);
const long long mod = (long long)1e9 + 7;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % mod;
    n = n * n % mod;
  }
  return r;
}
const int N = 3e5;
long long m, n, k;
int F[N][5], ans;
void Solve_by_hien2khy() {
  int q;
  cin >> q;
  for (int rrr = 1; rrr <= q; rrr++) {
    cin >> n >> k;
    string s;
    cin >> s;
    if (n == 1 || k == 1) {
      cout << "0\n";
      continue;
    }
    if (n == 2) {
      if (s == "BR" || s == "RG" || s == "GB")
        cout << "0\n";
      else
        cout << 1 << "\n";
      continue;
    }
    int B = 1, R = 2, G = 3, e = k % 3;
    ans = INT_MAX;
    if (s[0] != 'B') F[0][B] = 1;
    if (s[0] != 'R') F[0][R] = 1;
    if (s[0] != 'G') F[0][G] = 1;
    for (int i = 1; i < n; i++) {
      if (i < k) {
        if (s[i] == 'B') {
          F[i][B] = F[i - 1][G];
          F[i][R] = F[i - 1][B] + 1;
          F[i][G] = F[i - 1][R] + 1;
        }
        if (s[i] == 'R') {
          F[i][B] = F[i - 1][G] + 1;
          F[i][R] = F[i - 1][B];
          F[i][G] = F[i - 1][R] + 1;
        }
        if (s[i] == 'G') {
          F[i][B] = F[i - 1][G] + 1;
          F[i][R] = F[i - 1][B] + 1;
          F[i][G] = F[i - 1][R];
        }
      } else {
        int x;
        if (s[i - k] == 'B') x = 1;
        if (s[i - k] == 'R') x = 2;
        if (s[i - k] == 'G') x = 0;
        if (s[i] == 'B') {
          F[i][B] = F[i - 1][G] - ((B - e + 3) % 3 != x);
          F[i][R] = F[i - 1][B] + 1 - ((R - e + 3) % 3 != x);
          F[i][G] = F[i - 1][R] + 1 - ((G - e + 3) % 3 != x);
        }
        if (s[i] == 'R') {
          F[i][B] = F[i - 1][G] + 1 - ((B - e + 3) % 3 != x);
          F[i][R] = F[i - 1][B] - ((R - e + 3) % 3 != x);
          F[i][G] = F[i - 1][R] + 1 - ((G - e + 3) % 3 != x);
        }
        if (s[i] == 'G') {
          F[i][B] = F[i - 1][G] + 1 - ((B - e + 3) % 3 != x);
          F[i][R] = F[i - 1][B] + 1 - ((R - e + 3) % 3 != x);
          F[i][G] = F[i - 1][R] - ((G - e + 3) % 3 != x);
        }
      }
      if (i >= k - 1) ans = min(ans, min(F[i][B], min(F[i][R], F[i][G])));
    }
    cout << ans << "\n";
    for (int i = 0; i <= n; i++) {
      F[i][B] = F[i][R] = F[i][G] = 0;
    }
  }
}
int main(int argc, char** argv) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Solve_by_hien2khy();
  return 0;
}
