#include<bits/stdc++.h>
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 

#define ll long long
template<typename s, typename t> void smax(s &a, const t &b) {if (a<b) a=b;}
template<typename s, typename t> void smin(s &a, const t &b) {if (a>b) a=b;}
char gap = 32;

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define fill(x, y) memset(x, y, sizeof(x))
#define srt(v) sort(v.begin(), v.end())
#define rsrt(v) sort(v.rbegin(),v.rend())
#define pb push_back
#define lll __int128_t
ll hashPrime = 1610612741;

int cnt(const string &s) {
    int ct = 0;
    for (int i=0; i+2 < s.size(); i++) {
        if (s.substr(i, 3) == "abc") {
            ct++;
        }
    }
    return ct;
}

int cal(char a, char b, char c) {
    int sh = 0;
    sh += (26+ 'a' - a) % 26;
    sh += (26 +'b' - b) % 26;
    sh += (26 + 'c' - c) % 26;
    return sh;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int mx = cnt(s);
        for (int i=0; i+2<n; i++) {
            char a=s[i], b=s[i+1], c=s[i+2];
            int need = cal(a, b, c);
            if (need <= k) {
                k -= need;
                s[i] = 'a';
                s[i + 1] = 'b';
                s[i + 2] = 'c';
            }
        }
        mx = max(mx, cnt(s));
        cout << mx << endl;
    }
}