#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define dbg(a,b,c,d) cerr<<a<<"  "<<b<<"  "<<c<<"  "<<d<<endl;
#define kill(a) {cout<<a<<endl;continue;}
#define KILL(a) {cout<<a<<endl;return 0;}
#define debug cerr<<"Error Found"<<endl;
#define mem(a,b) memset(a,b,sizeof(a))
#define lcm(a, b) (a/__gcd(a,b))*b
#define w(t) cin>>t;while(t--)
#define pi  2 * acos(0.0)
#define endl "\n"
int t, cs = 0;
const int mxn = 2e5 + 2,mod = 1e9 + 7;

signed main()
{

    fast;
    w(t)
    {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        vector<pair<int,int>>v;
        for(int i = 0; i < n - 2; i++)
        {
            int a = s[i] - 'a', b = s[i + 1] - 'a', c = s[i + 2] - 'a';
            int d1, d2, d3;
            if(a > 0)d1 = 25 - a + 1;
            else d1 = 0;
            if(b > 1)d2 = 25 - b + 2;
            else d2 = abs(b - 1);
            if(c > 2)d3 = 25 - c + 3;
            else d3 = abs(2 - c);
            int cost = d1 + d2 + d3;
            v.push_back(make_pair(cost, i));
        }
        sort(v.begin(), v.end());
        bool vis[n + 1] = {};
        int ans = 0;
        for(auto i:v)
        {
            int cost = i.first, idx = i.second;
            if(cost > k)break;
            if(vis[idx] or vis[idx + 1] or vis[idx + 2])continue;
            vis[idx] = vis[idx + 1] = vis[idx + 2] = true;
            k -= cost;
            ans++;
        }
        cout << ans << endl;
    }
}