#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>;
long long base[2] = { 131, 13331 };
long long mod[2] = { 1000000007, 998244353 };
long long pw[400000 + 200][2];
void init()
{
    pw[0][0] = pw[0][1] = 1;
    for (int i = 0; i <= 400000; i++)
        for (int j = 0; j < 2; j++) {
            pw[i + 1][j] = pw[i][j] * base[j] % mod[j];
        }
}
void solve()
{
    int n,k;
    cin>>n>>k;
    string s,t;
    cin>>s;
    t = s;
    reverse(t.begin(),t.end());
    s = s + t;
    vector<vector<long long>> x(2 * n + 1,vector<long long>(2)), rx(2 * n + 1,vector<long long>(2));
    for (int i = 0; i < 2 * n; i++)
        for (int j = 0; j < 2; j++)
            x[i + 1][j] = (x[i][j] * base[j] + s[i]) % mod[j];
    auto gain = [&](int l, int r)->ll{
        pll ret;
        ret.fi = (x[r][0] - x[l - 1][0] * pw[r - l + 1][0] % mod[0] + mod[0]) % mod[0];
        ret.se = (x[r][1] - x[l - 1][1] * pw[r - l + 1][1] % mod[1] + mod[1]) % mod[1];
        return (ret.fi * 1000000000) ^ ret.se;
    };
    auto LCP = [&](int l1, int r1, int l2, int r2)->int{
        if(r1 < 0 || l2 > n)
            return 0;
        if(r1 - l1 + 1 <= 0 || r2 - l2 + 1 <= 0)
            return 0;
        l1 = 2 * n - l1 + 1,r1 = 2 * n - r1 + 1;
        swap(l1,r1);
        if(s[l1 - 1] != s[l2 - 1])
            return 0;
        int l = 1, r = min(r1 - l1 + 1, r2 - l2 + 1);
        while(l < r){
            int mid = (l + r + 1) >> 1;
            if(gain(l1, l1 + mid - 1) == gain(l2, l2 + mid - 1)) l = mid;
            else r = mid - 1;
        }
        return l;
    };
    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(1,lidx + 1,ridx + 1,n);
        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(1,Lidx + 1,rRidx + 1,n);
            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(1,rLidx + 1,Ridx + 1,n);
            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(1,lidx + 1,ridx + 1,n);
        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(1,Lidx + 1,rRidx + 1,n);
            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(1,rLidx + 1,Ridx + 1,n);
            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(1,Lidx + 1,rRidx + 1,n);
            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(1,rLidx + 1,Ridx + 1,n);
            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;
    init();
    while(T --)
        solve();
}