#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define f first
#define s second
void solve () {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = '#' + s;
    int c[n + 1] = {};
    for (int i = 1; i + 2 <= n; ++i) {
        if (s[i] != 'a') {
            c[i] += ('z' - s[i]) + 1;
        }
        if (s[i + 1] <= 'b') {
            c[i] += ('b' - s[i + 1]);
        } else {
            c[i] += ('z' - s[i + 1]) + 2;
        }
        if (s[i + 2] <= 'c') {
            c[i] += ('c' - s[i + 2]);
        } else {
            c[i] += ('z' - s[i + 2]) + 3;
        }
    }
    vector <vector <int>> dp(n + 1, vector <int> (n + 1, 1e18));
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 0;
    }
    for (int i = 1; i + 2 <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            dp[i + 2][j] = min(dp[i + 2][j], dp[i + 1][j]);
            if (j + 1 <= n) {
                dp[i + 2][j + 1] = min(dp[i + 2][j + 1], dp[i - 1][j] + c[i]);
            }
        }
    }
    for (int i = n; i >= 0; --i) {
        if (dp[n][i] <= k) {
            cout << i << endl;
            return;
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}