#include <bits/stdc++.h>

using namespace std;

void solve(int cs) {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  k = min(k, n * 25);
  vector<vector<vector<int>>> dp(n, vector<vector<int>> (k + 1, vector<int>(3, -1)));
  auto go = [&](auto &&self, int i, int ops, int last) -> int {
    if (i == n) return 0;
    if (dp[i][ops][last] != -1) return dp[i][ops][last];
    int ret = self(self, i + 1, ops, 2);
    if (last == 2) {
      int needOps = 0;
      int d = s[i] - 'a';
      while (d != 0) {
        d += 1;
        needOps += 1;
        d %= 26;
      }
      if (needOps <= ops) {
        ret = max(ret, self(self, i + 1, ops - needOps, 0));
      }
    }
    if (last == 0) {
      int needOps = 0;
      int d = s[i] - 'a';
      while (d != 1) {
        d += 1;
        needOps += 1;
        d %= 26;
      }
      if (needOps <= ops) {
        ret = max(ret, self(self, i + 1, ops - needOps, last + 1));
      }
    }
    if (last == 1) {
      int needOps = 0;
      int d = s[i] - 'a';
      while (d != 2) {
        d += 1;
        needOps += 1;
        d %= 26;
      }
      if (needOps <= ops) {
        ret = max(ret, self(self, i + 1, ops - needOps, last + 1) + 1);
      }
    }
    return dp[i][ops][last] = ret;
  };

  cout << go(go, 0, k, 2) << "\n";
}

int32_t main() {
  cin.tie(0) -> sync_with_stdio(0);
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}