#ifndef LOCAL
#include <bits/stdc++.h>
#define debug(...)
#endif

using namespace std;
#define int long long
#define cinv(v) for (auto &it:v) cin>>it;
#define coutv(v) for (auto &it:v) cout<< it<<' '; cout<<'\n';

const int INF = 1e8;

void shelby() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<array<int, 3> > need(n);
    auto calc = [&](char x, char y)-> int {
        if (y >= x) return y - x;
        return 26 - (x - y);
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) need[i][j] = calc(s[i], 'a' + j);
    }
    auto ok = [&](int x)-> bool {
        vector memo(n, vector<int>(x + 1, -1));
        auto dp = [&](auto &&self,int i, int rem)-> int {
            if (rem == 0) return 0;
            if (i + 2 >= n) return INF;
            auto &ret = memo[i][rem];
            if (~ret) return ret;
            ret = self(self, i + 1, rem);
            ret = min(ret, need[i][0] + need[i + 1][1] + need[i + 2][2] + self(self, i + 1, rem - 1));
            return ret;
        };
        return dp(dp, 0, x) <= k;
    };
    int l = 0, r = n / 3, ans = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        if (ok(m)) ans = m, l = m + 1;
        else r = m - 1;
    }
    cout << ans << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case " << _ << ": ";
        shelby();
    }
}