#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int dp[5005][5005];
char A[5005];

int cst(char x, char y){
	if(x <= y)return y - x;
	else return y - x + 26;
}

void solve(){
	int n, k; cin >> n >> k;
	for(int i = 1; i <= n; i++)cin >> A[i];
	for(int i = 0; i <= 2; i++)for(int j = 1; j <= n; j++)dp[i][j] = 1e18;
	for(int i = 3; i <= n; i++){
		for(int j = 1; j <= n; j++){
			dp[i][j] = min(dp[i - 1][j], dp[i - 3][j - 1] + cst(A[i - 2], 'a') + cst(A[i - 1], 'b') + cst(A[i], 'c'));
		}
	}
	for(int i = n; i >= 0; i--){
		if(dp[n][i] <= k){
			cout << i << '\n';
			return;
		}
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}