#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;
vector<vector<int>>dp(limit,vector<int>(limit,k+1));
cin>>s;
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;
}