#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
int main()
{
    ll tc;
    cin>>tc;
    while(tc--)
    {
        ll n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        vector<pair<ll,ll>>u;
        for(int i=0;i<s.size()-2;i++)
        {
            string l;
            l="abc";
            ll cst=0;
            if(s[i]<=l[0])
             cst+=(l[0]-s[i]);
            else
                cst+=(('z'-s[i])+1+(l[0]-'a'));
             if(s[i+1]<=l[1])
             cst+=(l[1]-s[i+1]);
            else
                cst+=(('z'-s[i+1])+1+(l[1]-'a'));
              if(s[i+2]<=l[2])
             cst+=(l[2]-s[i+2]);
            else
                cst+=(('z'-s[i+2])+1+(l[2]-'a'));
            u.push_back({cst,i});
        }
        sort(u.begin(),u.end());
        ll ans=0;
    map<ll,ll>mp;
        for(int i=0;i<u.size();i++)
        {
            if(u[i].first<=k && mp[u[i].second]==0 && mp[u[i].second+1]==0 && mp[u[i].second+2]==0)
            {
                ans++;
                k-=u[i].first;
                mp[u[i].second]++;
                mp[u[i].second+1]++;
                mp[u[i].second+2]++;
            }
        }
        cout<<ans<<endl;
    }
    
}