// PIPRA ||  HABIB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define int        long long int
#define pb         push_back
#define all(x)     x.begin(),x.end()
#define allr(x)    x.rbegin(),x.rend()
#define ii         pair<int,int>
#define endl       "\n"

template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) {
    os << '{';
    for (const auto &x : v) os << " " << x;
        return os << '}';
}
using orderedTree = tree<int, null_type, less<int>, 
rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5005;
const int inf = 1e8;

int n;
string s;
vector<vector<int>> dp(N, vector<int>(N));

int recur(int i, int cnt){
    if(cnt == 0)    return 0;
    if(i >= (n-2))  return inf;

    int &ans = dp[i][cnt];
    if(ans != -1)   return ans;

    ans = recur(i+1, cnt);

    
    int ind = i;
    int cost = 0;
    for(char ch='a' ; ch<='c' ; ch++){
        if(s[ind] <= ch){
            cost += ch - s[ind];
        }
        else{
            cost += 'z' - s[ind] + (ch - 'a' + 1);
        }
        ind++;
    }

    ans = min(ans, cost + recur(i+3, cnt-1));
    return ans;
}

void pipra(){
    int k;
    cin >> n >> k;
    cin >> s;

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

    for(int i=n ; i>=1 ; i--){
        int x = recur(0, i);
        if(x <= k){
            cout << i << endl;
            return;
        }
    }

    cout << 0 << endl;
}

int32_t main(){
    // HABIB
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

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