#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, k;
string s;
int memo[2010][2010][4];
bool vis[2010][2010][4];
int go(int pos, int sz, int lastw) {
  if (sz >= k) {
    return 0;
  }
  if (pos >= n) {
    return INF;
  }
  if (vis[pos][sz][lastw]) {
    return memo[pos][sz][lastw];
  }
  int res1 = INF, res2 = INF, res3 = INF, res4 = INF, best = INF;
  if (lastw == 0 or lastw == 3) {
    res1 = go(pos + 1, sz + 1, 1);
    if (s[pos] != 'R') {
      res1++;
    }
  }
  if (lastw == 0 or lastw == 1) {
    res2 = go(pos + 1, sz + 1, 2);
    if (s[pos] != 'G') {
      res2++;
    }
  }
  best = min(res1, res2);
  if (lastw == 0 or lastw == 2) {
    res3 = go(pos + 1, sz + 1, 3);
    if (s[pos] != 'B') {
      res3++;
    }
  }
  res4 = go(pos + 1, 0, 0);
  best = min(best, min(res3, res4));
  memo[pos][sz][lastw] = best;
  vis[pos][sz][lastw] = 1;
  return best;
}
int main() {
  int Q;
  cin >> Q;
  while (Q--) {
    cin >> n >> k >> s;
    cout << go(0, 0, 0) << endl;
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= k; j++) {
        for (int f = 0; f < 4; f++) {
          vis[i][j][f] = 0;
        }
      }
    }
  }
  return 0;
}
