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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
using ll = long long;

const int INF = 100'000'000;
const int MX = 5005;
int dp[MX][MX];
int a[MX][3];
int n, k;
string s;

int solve(int ind, int cnt) {
  if (cnt == 0) return 0;
  if (ind >= n-2) return INF;

  int& curr = dp[ind][cnt];
  if (curr != -1) return curr;

  curr = solve(ind+1, cnt);
  curr = min(curr, a[ind][0] + a[ind+1][1] + a[ind+2][2] + solve(ind+3, cnt-1));

  return curr;
}

int main() {
  FAST;
  
  int tc = 1, ti;
  cin >> tc;

  for (ti = 1; ti <= tc; ++ti) {
    int i, j, x;
    cin >> n >> k;
    cin >> s;

    for (i = 0; i <= n; ++i) {
      for (j = 0; j <= n; ++j) dp[i][j] = -1;
    }

    for (i = 0; i < n; ++i) {
      for (j = 0; j < 3; ++j) {
        x = s[i]-'a';
        x = j-x;
        if (x < 0) x += 26;
        a[i][j] = x;
      }
    }

    for (i = n; i >= 1; --i) {
      if (solve(0, i) <= k) break;
    }

    cout << i << "\n";
  }

  return 0;
}