#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fi first
#define se second
using ll = long long;
using pll = pair<ll,ll>;
using i64 = long long;
struct SA {
    int n;
    std::vector<int> sa, rk, lc;

    SA(std::string s) {
        n = s.size();
        sa.resize(n);
        lc.resize(n - 1);
        rk.resize(n);
        std::iota(sa.begin(), sa.end(), 0);
        std::sort(sa.begin(), sa.end(),
            [&](int a, int b) {
                return s[a] < s[b];
            });
        rk[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
        }
        int k = 1;
        std::vector<int> tmp, cnt(n);
        tmp.reserve(n);
        while (rk[sa[n - 1]] < n - 1) {
            tmp.clear();
            for (int i = 0; i < k; i++) {
                tmp.push_back(n - k + i);
            }
            for (auto i : sa) {
                if (i >= k) {
                    tmp.push_back(i - k);
                }
            }
            std::fill(cnt.begin(), cnt.end(), 0);
            for (int i = 0; i < n; i++) {
                cnt[rk[i]]++;
            }
            for (int i = 1; i < n; i++) {
                cnt[i] += cnt[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
                sa[--cnt[rk[tmp[i]]]] = tmp[i];
            }
            std::swap(rk, tmp);
            rk[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
            }
            k *= 2;
        }
        for (int i = 0, j = 0; i < n; i++) {
            if (rk[i] == 0) {
                j = 0;
            } else {
                for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j]; ) {
                    j++;
                }
                lc[rk[i] - 1] = j;
            }
        }
    }
};

void solve()
{
    int n,k;
    cin>>n>>k;
    string s,t;
    cin>>s;
    t = s;
    reverse(t.begin(),t.end());
    s = s + t;
    SA sa(s);
    // cout<<s<<"\n";
    int m = sa.lc.size();
    int lgm = std::__lg(m);

    std::vector st(lgm + 1, std::vector<int>(m));
    st[0] = sa.lc;
    for (int j = 0; j < lgm; j++) {
        for (int i = 0; i + (2 << j) <= m; i++) {
            st[j + 1][i] = std::min(st[j][i], st[j][i + (1 << j)]);
        }
    }

    auto rmq = [&](int l, int r) {
        int k = std::__lg(r - l);
        return std::min(st[k][l], st[k][r - (1 << k)]);
    };

    auto LCP = [&](int i, int j) {
        if(i < 0 || j >= n)
            return 0;
        int x = sa.rk[j], y = sa.rk[n + n - i - 1];
        if (x > y) {
            std::swap(x, y);
        }
        return std::min({n - j, i + 1, rmq(x, y)});
    };
    int ans = 0;
    for(int i = 0;i < n;i ++)
    {
        int Lmx = i,Rmx = n - 1 - i;
        int lidx = i - 1,ridx = i + 1;
        int lcp1 = LCP(lidx,ridx);
        int Lidx = lidx - lcp1,Ridx = ridx + lcp1;
        Lmx -= lcp1,Rmx -= lcp1;
        for(int j = 1;j <= min(Rmx,k);j ++)
        {
            int rRidx = Ridx + j;
            int lcp2 = LCP(Lidx,rRidx);
            int lasL = Lidx - lcp2 + 1,lasR = rRidx + lcp2 - 1;
            ans = max(ans,lasR - lasL + 1 + j);
        }
        for(int j = 1;j <= min(Lmx,k);j ++)
        {
            int rLidx = Lidx - j;
            int lcp2 = LCP(rLidx,Ridx);
            int lasL = rLidx - lcp2 + 1,lasR = Ridx + lcp2 - 1;
            ans = max(ans,lasR - lasL + 1 + j);
        }
    }
    for(int i = 0;i < n;i ++)
    {
        int Lmx = i,Rmx = n - i;
        int lidx = i - 1,ridx = i;
        int lcp1 = LCP(lidx,ridx);
        int Lidx = lidx - lcp1,Ridx = ridx + lcp1;
        Lmx -= lcp1,Rmx -= lcp1;
        for(int j = 1;j <= min(Rmx,k);j ++)
        {
            int rRidx = Ridx + j;
            int lcp2 = LCP(Lidx,rRidx);
            int lasL = Lidx - lcp2 + 1,lasR = rRidx + lcp2 - 1;
            ans = max(ans,lasR - lasL + 1 + j);
        }
        for(int j = 1;j <= min(Lmx,k);j ++)
        {
            int rLidx = Lidx - j;
            int lcp2 = LCP(rLidx,Ridx);
            int lasL = rLidx - lcp2 + 1,lasR = Ridx + lcp2 - 1;
            ans = max(ans,lasR - lasL + 1 + j);
        }
    }
    for(int i = 0;i < n;i ++)
    {
        int Lmx = i,Rmx = n - i;
        int lidx = i - 1,ridx = i;
        int Lidx = lidx,Ridx = ridx;
        for(int j = 1;j <= min(Rmx,k);j ++)
        {
            int rRidx = Ridx + j;
            int lcp2 = LCP(Lidx,rRidx);
            int lasL = Lidx - lcp2 + 1,lasR = rRidx + lcp2 - 1;
            ans = max(ans,lasR - lasL + 1 + k);
        }
        for(int j = 1;j <= min(Lmx,k);j ++)
        {
            int rLidx = Lidx - j;
            int lcp2 = LCP(rLidx,Ridx);
            int lasL = rLidx - lcp2 + 1,lasR = Ridx + lcp2 - 1;
            ans = max(ans,lasR - lasL + 1 + k);
        }
    }
    cout<<ans<<"\n";    
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    cin>>T;
    while(T --)
        solve();
}