#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define dbg(a,b,c,d) cerr<<a<<"  "<<b<<"  "<<c<<"  "<<d<<endl;
#define kill(a) {cout<<a<<endl;continue;}
#define KILL(a) {cout<<a<<endl;return 0;}
#define debug cerr<<"Error Found"<<endl;
#define mem(a,b) memset(a,b,sizeof(a))
#define lcm(a, b) (a/__gcd(a,b))*b
#define w(t) cin>>t;while(t--)
#define pi  2 * acos(0.0)
#define endl "\n"
int t, cs = 0;
const int mxn = 5e3 + 3, mod = 1e9 + 7;
int vis[mxn][mxn], dp[mxn][mxn];
int n, k;
string s;
int cost(int ch, int turn)
{
    if(turn == 0)
    {
        if(!ch)return ch;
        return 25 - ch + 1;
    }
    else if(turn == 1)
    {
        if(ch <= 1)return 1 - ch;
        return 25 - ch + 2;
    }
    else
    {
        if(ch <= 2)return 2 - ch;
        return 25 - ch + 2;
    }

}
int rec(int i, int cnt)
{
    if(!cnt)return 0;
    if(i >= n - 2)return 1e9;
    if(vis[i][cnt] == cs)return dp[i][cnt];
    vis[i][cnt] = cs;
    int ans = 1e9;
    int a = cost(s[i] - 'a', 0), b = cost(s[i + 1] - 'a', 1), c = cost(s[i + 2] - 'a', 2);
    ans = min(ans, a + b + c + rec(i + 3, cnt - 1));
    ans = min(ans, rec(i + 1, cnt));
    return dp[i][cnt] = ans;
}
int32_t main()
{
    //fast;
    w(t)
    {
        cin >> n >> k;
        cin >> s;
        int low = 1, high = n / 3;
        while(low <= high)
        {
            int mid = low + high >> 1;
            ++cs;
            int cost = rec(0, mid);

            if(cost <= k)low = mid + 1;
            else high = mid - 1;
        }
        cout << --low << endl;
    }

}