#include<bits/stdc++.h>
using namespace std;
const long long M=2e3+1,MOD=1000000000;
typedef long long ll;
//int dp[5001][5001];
int limit=5001;
int find_cost(char a, char b, char c){
    int total=0;
    while(a!='a'){
        total++;
        if(a=='z')a='a';
        else a++;
    }
    while(b!='b'){
        if(b=='z')b='a';
        else b++;
        total++;
    }
    while(c!='c'){
        if(c=='z')c='a';
        else c++;
        total++;
    }
    return total;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        vector<pair<int,int>>st;
        for(int i=3;i<=n;i++){
            int cost=find_cost(s[i-3],s[i-2],s[i-1]);// cost for each substring
            st.push_back({cost,i});
        }
        vector<int>fre(3*n+1,0);
        sort(st.begin(),st.end());
        int res=0;
       for(int i=0;i<(int)st.size()&&k>0;i++){
          int x=st[i].second;
          int y=st[i].first;
          int tot=3;
          int xx=1;
          while(tot>0){
            tot--;
            xx&=(fre[x]==0);
            x--;
          }
          if(xx && y<=k){
            res++;
            x=st[i].second;
            k-=y;
            fre[x]=fre[x-1]=fre[x-2]=1;

          }
       }
       cout<<res<<"\n";
        

       
    }


   return 0;
 
}