#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define f(i,x,y) for(int i=x;i<y;i++)
#define f2(i,x,y) for(int i=x;i>=y;i--)
#define pii pair<int,int>
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int MOD =1000000007;
const int INF = 1000000000;
const int N = 5005;
int dp[N][N],mn_cost[N][3];
int n,k;
string s;
// int fun(int ind,int cnt){
//     if(cnt==0)return 0;
//     if(ind+2>=n)return INF;
//     if(dp[ind][cnt]!=-1)return dp[ind][cnt];
//     int way1 = fun(ind+1,cnt);
//     int way2 = mn_cost[ind][0] + mn_cost[ind+1][1] + mn_cost[ind+2][2] + fun(ind+3,cnt-1);
//     return dp[ind][cnt] = min(way1,way2);
// }
int fun(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 = fun(ind+1, cnt);
  curr = min(curr, mn_cost[ind][0] + mn_cost[ind+1][1] + mn_cost[ind+2][2] + fun(ind+3, cnt-1));

  return curr;
}
void solve(int tc){
    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;
        mn_cost[i][j] = x;
      }
    }

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

    cout << i << "\n";

}
int32_t main(){

    Fast

    int t=1;

    cin >> t;

    for(int tc=1;tc<=t;tc++){

        solve(tc);
    }
    return 0;
}