#include<bits/stdc++.h>
using namespace std;
const long long M=2e3+1,MOD=1000000000;
typedef long long ll;
int dp[5001][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;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)dp[i][j]=k+1;
            for(int j=0;j<=n;j++)dp[j][0]=0;// base case
        for(int i=3;i<=n;i++){
            int cost=find_cost(s[i-3],s[i-2],s[i-1]);// cost for each substring
            int left_index=i-3;
            for(int j=n-2;j>=1;j--){
                dp[i][j]=min(dp[left_index][j],dp[left_index][j-1]+cost);
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
            }
        }
        int res=0;
        for(int i=1;i<=n;i++)if(dp[n][i]<=k)res=i;
            cout<<res<<"\n";

       
    }


   return 0;
 
}