#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int K = 21;
const int INF = 1e9;

int n, k;
string s;
int dp[N][K][K][2]; // 0: O, 1: K

void solve() {
  cin >> n >> k >> s;
  s = " " + s;

  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= k; ++j) {
      for (int l = 0; l <= k; ++l) {
        for (int m = 0; m < 2; ++m) {
          dp[i][j][l][m] = -INF;
        }
      }
    }
  }

  if (s[1] == 'O') {
    dp[1][0][0][0] = 1;
  } else {
    dp[1][0][1][0] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    for (int ok = 0; ok <= k; ++ok) {
      for (int ko = 0; ko <= k; ++ko) {
        for (int last = 0; last < 2; ++last) {
          if (dp[i][ok][ko][last] == -INF) {
            continue;
          }

          // cerr << i << ' ' << ok << ' ' << ko << ' ' << last << ' ' << dp[i][ok][ko][last] << '\n';
          // if (i == n) {
          //   continue;
          // }

          int cur = s[i + 1] == 'O' ? 0 : 1;
          dp[i + 1][ok][ko][cur] = max(dp[i + 1][ok][ko][cur], dp[i][ok][ko][last] + (last != cur));
          if (cur == 0 && ok < k) {
            dp[i + 1][ok + 1][ko][1] = max(dp[i + 1][ok + 1][ko][1], dp[i][ok][ko][last] + (last != 1));
          }
          if (cur == 1 && ko < k) {
            dp[i + 1][ok][ko + 1][0] = max(dp[i + 1][ok][ko + 1][0], dp[i][ok][ko][last] + (last != 0));
          }

          if (ok < k && ko < k) {
            dp[i][ok + 1][ko + 1][last] = max(dp[i][ok + 1][ko + 1][last], dp[i][ok][ko][last]);
          }
        }
      }
    }
  }

  int cntO = 0, cntK = 0;
  for (int i = 1; i <= n; ++i) {
    if (s[i] == 'O') {
      ++cntO;
    } else {
      ++cntK;
    }
  }

  int res = 0;
  int len, oo, kk;

  for (int i = 0; i <= k; i++) {
    int len = dp[n][i][i][1];
    if (len > 0) {
      //cerr << "len1 = " << len << '\n';
      // oo = cntO - len / 2;
      // kk = cntK - len / 2;
      res = max(res, len - 1); // + oo - kk);
    }
  }
  cout << res << '\n';
}   

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); 

  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

/*
4
2 1
KO
7 1
OOOKKKK
7 1
KKOOKKK
10 2
KOOKOKKKOO
*/