#include<bits/stdc++.h>
using namespace std;
const long long M=3e5+10,MOD=1000000007;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
     int n,k;
     cin>>n>>k;
     string s;
     cin>>s;
     int res=0;
     for(char ch='a';ch<='z';ch++){
        string p="";
        char c=ch;
        int tt=26;
        while(tt>0){
            p+=c;
            if(c=='z')c='a';
            else c++;
            tt--;
        }
        int l=0;
        vector<vector<int>>dp(n+1,vector<int>(26,0));
        for(int i=0;i<n;i++){
            int j=i;
            int r=0;
            int cnt=0;
            while(j<n&& r<p.size()){
                cnt+=(s[j]!=p[r]);
                dp[i][r]=cnt;
                j++,r++;
            }
            while(r<26)dp[i][r]=cnt,r++;
            //dp[i]=cnt;
        }
        for(int j=0;j<min(26,n);j++){
          int l=j;
          int r=j;
          int cur=0;
          int limit=26;
          tt=k;
          while(r<n){
                int temp=0;
                int extra=0;
                int kk=r;
                while(temp<=25&& dp[r][temp]<=tt && kk<n){
                    temp++;
                    extra++;
                    kk++;
                }
                res=max(res,cur+extra);
                tt-=dp[r][25];
                cur+=min(limit,n-r);
                while(l<=r && tt<0){
                    cur-=min(26,n-r);
                    tt+=dp[l][25];
                    l+=limit;
                    l=min(n-1,l);
                }
                res=max(res,cur);
                if(r==n-1)break;
                r+=limit;
                r=min(r,n-1);
            }
          }
        }
       cout<<res<<"\n";
     
    }
    
   
   return 0;
    
}