#include <bits/stdc++.h>
using namespace std;
int inf = INT_MAX;
long long modulo(long long num, long long MOD = 998244353) {
  return ((num % MOD) + MOD) % MOD;
}
long long power(long long b, long long e, long long MOD = 998244353) {
  long long ans = 1;
  while (e) {
    if (e % 2) ans = (ans * b) % MOD;
    b = (b * b) % MOD;
    e /= 2;
  }
  return ans;
}
long long inv(long long num, long long MOD = 998244353) {
  return power(modulo(num), MOD - 2, MOD);
}
long long gcd(long long a, long long b) {
  return ((b == 0) ? a : gcd(b, a % b));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> q;
  while (q-- > 0) {
    long long n, k;
    cin >> n >> k;
    string str;
    cin >> str;
    long long ans[n + 1][3], arr[n + 1][3];
    memset(ans, 0, sizeof(ans));
    memset(arr, 0, sizeof(arr));
    for (int i = n; i > 0; i--) {
      if (i == n) {
        ans[i][0] = 1;
        ans[i][1] = 1;
        ans[i][2] = 1;
        if (str[i - 1] == 'R') {
          ans[i][0] = 0;
        } else if (str[i - 1] == 'G') {
          ans[i][1] = 0;
        } else {
          ans[i][2] = 0;
        }
      } else if (n - i + 1 <= k) {
        ans[i][0] = ans[i + 1][1] + 1;
        ans[i][1] = ans[i + 1][2] + 1;
        ans[i][2] = ans[i + 1][0] + 1;
        arr[i][0] = ans[i + 1][1] + 1;
        arr[i][1] = ans[i + 1][2] + 1;
        arr[i][2] = ans[i + 1][0] + 1;
        if (str[i - 1] == 'R') {
          ans[i][0]--;
          arr[i][0]--;
        } else if (str[i - 1] == 'G') {
          ans[i][1]--;
          arr[i][1]--;
        } else {
          ans[i][2]--;
          arr[i][2]--;
        }
      } else {
        ans[i][0] = ans[i + 1][1] + 1;
        ans[i][1] = ans[i + 1][2] + 1;
        ans[i][2] = ans[i + 1][0] + 1;
        arr[i][0] = ans[i + 1][1] + 1 - ans[i + k][k % 3];
        arr[i][1] = ans[i + 1][2] + 1 - ans[i + k][(k + 1) % 3];
        arr[i][2] = ans[i + 1][0] + 1 - ans[i + k][(k + 2) % 3];
        if (str[i - 1] == 'R') {
          ans[i][0]--;
          arr[i][0]--;
        } else if (str[i - 1] == 'G') {
          ans[i][1]--;
          arr[i][1]--;
        } else {
          ans[i][2]--;
          arr[i][2]--;
        }
      }
    }
    long long m = inf;
    for (int i = 1; i <= n - k + 1; i++) {
      m = min(m, min(arr[i][0], min(arr[i][2], arr[i][1])));
    }
    cout << m << "\n";
  }
  return 0;
}
