#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());
/*_________________________________________________________________________________________________________________________*/

vector<vector<ll>> dp(100001 + 1, vector<ll>(26, 0));
vector<ll> arr[26];
void Solve()
{
    ll n, k;
    cin >> n >> k;
    string a;
    cin >> a;
    for (int i = 0; i < 26; i++)
        arr[i].clear();
    for (int i = 0; i < n; i++) {
        for (char c = 'a'; c <= 'z'; c++) {
            if (c != a[i])
                dp[i][c - 'a'] = 1;
            else
                dp[i][c - 'a'] = 0;
        }
    }
    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;
        }
    }
    ll ans = 1;
    for (int m = 0; m < 26; 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 {
                sum -= arr[m][i];
                i++;
            }
        }
    }
    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)