#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
#define sz(x) (ll)(x).size()
#define rd ({ll x; cin >> x; x; })
#define dbg(x) cerr << "[" #x "]  " << (x) << "\n\n"
#define errv(x)                     \
    {                               \
        cerr << "[" #x "]  [";      \
        for (const auto& ___ : (x)) \
            cerr << ___ << ", ";    \
        cerr << "]\n";              \
    }
// #define errvn(x, n) {cerr << "["#x"]  ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
// #define cerr if(0)cerr
#define xx first
#define yy second
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
/*_________________________________________________________________________________________________________________________*/

void Solve()
{
    ll n, k;
    cin >> n >> k;
    vector<vector<ll>> dp(n + 1, vector<ll>(26, 0));
    string a;
    cin >> a;
    // vector<vector<ll>> arr(26, vector<ll>()), bk;
    vector<ll> arr[26];
    // for (char c = 'a'; c <= 'z'; c++) {
    //     arr[c - 'a'].push_back(a[0] != c);
    // }
    for (int i = 0; i < n; i++) {
        // for (char c = 'a'; c <= 'z'; c++) {
        //     if (c == 'a') {
        //         arr[25].push_back(a[i] != c);
        //     } else {
        //         arr[c - 'a' - 1].push_back(a[i] != c);
        //     }
        // }
        for (char c = 'a'; c <= 'z'; c++) {
            if (c != a[i])
                dp[i][c - 'a'] = 1;
        }
    }
    for (int m = 0; m < 26; m++) {
        ll i = m;
        for (int j = 0; j < n; j++) {
            arr[m].push_back(dp[j][i]);
            i = (i + 1) % 26;
        }
    }

        // for (int i = 1; i < n; i++) {
        //     // for (char c = 'a'; c <= 'z'; c++) {
        //     //     if (c == 'a')
        //     //         dp[i][c - 'a'] += dp[i - 1][25];
        //     //     else
        //     //         dp[i][c - 'a'] += dp[i - 1][c - 'a' - 1];
        //     // }
        //     for (char c = 'a'; c <= 'z'; c++) {
        //         if (c == 'a') {
        //             arr[25].push_back(a[i] != c);
        //         } else {
        //             arr[c - 'a' - 1].push_back(a[i] != c);
        //         }
        //     }
        // }
        // bk = arr;
        ll ans = 1;
    for (int m = 0; m < 26; m++) {
        // for (int i = 1; i < n; i++)
        //     arr[m][i] += arr[m][i - 1];
        // for (int i = 0; i < n; i++) {
        //     ll toSearch = k + (i ? arr[m][i - 1] : 0);
        //     auto it = --upper_bound(arr[m].begin(), arr[m].end(), toSearch);
        //     ll idx = it - arr[m].begin();
        //     ans = max(ans, idx - i + 1);
        // }
        errv(arr[m]);
        dbg(sz(arr[m]));
        ll i = 0, j = 0, sum = arr[m][0];
        while (j < n && i < n) {
            if (sum <= k) {
                ans = max(ans, j - i + 1);
                j++;
                if (j < n)
                    sum += arr[m][j];
                else
                    break;
            } else {
                sum -= arr[m][i];
                i++;
            }
        }
        dbg(ans);
    }
    // for (int i = 0; i < n - 1; i++) {
    //     for (char c = 'a'; c <= 'z'; c++) {
    //         ll lo = 1, hi = n - i - 1;
    //         while (lo <= hi) {
    //             ll mid = (lo + hi) / 2;
    //             ll mod1 = mid % 26;
    //             ll targetChar = (c - 'a' + mod1) % 26;
    //             ll cost = dp[i + mid][targetChar] - (i ? dp[i][c - 'a'] : 0);
    //             if (cost <= k) {
    //                 lo = mid + 1;
    //                 ans = max(ans, mid);
    //             } else
    //                 hi = mid - 1;
    //         }
    //     }
    // }
    cout << ans << "\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": "; // cout << "Case " << i << ": ";
        Solve();
    }
    return 0;
}
// Coded by Tahsin Arafat (@TahsinArafat)