#include<bits/stdc++.h>
#define endl        '\n'
#define F           first
#define S           second
#define pb          push_back
#define yes         cout<<"YES\n"
#define no          cout<<"NO\n"
#define all(x)      x.begin(),x.end()
#define allr(x)     x.rbegin(),x.rend()
#define error1(x)   cerr<<#x<<" = "<<(x)<<endl
#define error2(a,b) cerr<<"("<<#a<<", "<<#b<<") = ("<<(a)<<", "<<(b)<<")\n";
#define coutall(v)  for(auto &it: v) cout << it << " "; cout << endl;
using namespace std;
using ll = long long;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

// for gp_hash_table and unordered_map
struct custom_hash { 
    static uint64_t splitmix64(uint64_t x) {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x += FIXED_RANDOM;
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const { // x key
        return splitmix64(x);
    }
    size_t operator()(pair<uint64_t, uint64_t> x) const { // For, key = pair
        return splitmix64(x.first) ^ splitmix64(x.second);
    }
};

// gp_hash_table<pair<ll, int>, int, pair_hash> gph;
// gp_hash_table<char, int, custom_hash> gph;

void solve() {
    int n, k;
    string s1;
    cin >> n >> k >> s1;
    
    gp_hash_table<pair<int, int>, int, custom_hash> mp;
    auto rec = [&](auto&& self, int i, int k) -> int {
        if(i + 2 >= n) return 0;
        auto it = mp.find(make_pair(i, k));
        if(it != mp.end()) return it->S;
        int ans = self(self, i + 1, k);

        int cost = 0;
        if(s1[i] != 'a') cost += ('z' - s1[i]) + 1;
        if(s1[i + 1] != 'b') {
            if(s1[i + 1] == 'a') cost += 1;
            else cost += ('z' - s1[i + 1]) + 2; 
        }
        if(s1[i + 2] != 'c') {
            if(s1[i + 2] == 'a') cost += 2;
            else if(s1[i + 2] == 'b') cost += 1;
            else cost += ('z' - s1[i + 2]) + 3; 
        }
        // cout << i << " => " << cost << endl;
        if(cost <= k) ans = max(ans, 1 + self(self, i + 3, k - cost));
        return mp[{i, k}] = ans;
    };
    cout << rec(rec, 0, k) << endl;
    return;
}

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