#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr freopen ("input19.txt","r",stdin)
//ofstream file("output19.txt");

bool check(vector<vector<int>> &dp,int n,int k,int mid)
{
    for(int i=0;i<26;i++)
    {
        if(dp[i][mid-1] <= k) return true;
        for(int j=mid;j<n;j++)
        {
            if(dp[i][j] - dp[i][j-mid] <= k) return true;
        }
    } 
    return false;
}

void solve()
{
    int n,k; cin>>n>>k;
    string s; cin>>s;
    // hashing the characters
    int ch[26];
    for(int i=0;i<26;i++) ch[i] = i;
    vector<vector<int>> dp(26,vector<int>(n));

    // mapping the next character
    map<int,int> mp;
    for(int i=0;i<25;i++) mp[i]=i+1;
    mp[25] = 0;

    // first row of dp
    for(int i=0;i<26;i++) dp[i][0] = ((s[0]-'a') != i);
    
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<26;j++)
        {
            // shifting characters to the next
            ch[j] = mp[ch[j]];
            dp[j][i] = dp[j][i-1] + (s[i]-'a' != ch[j]);
        }
    }

    /*for(int i=0;i<26;i++)
    {
        for(int j=0;j<n;j++) cout<<dp[i][j]<<" "; cout<<endl;
    }*/
    
    int ans = 0,lo = 0, hi = n, mid;
    while(lo<=hi)
    {
        mid = (lo+hi)/2;
        if(check(dp,n,k,mid))
        {
            ans = max(ans,mid);
            lo = mid + 1;
        }
        else hi = mid - 1;
    }
    
    cout<<ans<<endl;
    //file<<ans<<endl;
}

int main()
{
    //fr;
    int t; cin>>t; while(t--) solve();
}