#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
const int N=4e5+50;

void build(const char *s,int n,int *sa,int *rk,int *h) {
    static int _sa[N],A[N],B[N],cnt[max(300,N)];
    int m=260;
    FOR(i,0,m) cnt[i]=0;
    FOR(i,1,n) ++cnt[s[i]];
    FOR(i,1,m) cnt[i]+=cnt[i-1];
    DOR(i,n,1) sa[cnt[s[i]]--]=i;
    rk[sa[1]]=1;
    FOR(i,2,n) rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);
    for(int l=1; l<n && (m=rk[sa[n]])<n; l<<=1) {
        FOR(i,1,n) A[i]=(i+l<=n)?rk[i+l]:0;
        FOR(i,1,n) B[i]=rk[i];
        int p=0;
        FOR(i,n-l+1,n) _sa[++p]=i;
        FOR(i,1,n) if(sa[i]>l) _sa[++p]=sa[i]-l;
        FOR(i,0,m) cnt[i]=0;
        FOR(i,1,n) ++cnt[B[_sa[i]]];
        FOR(i,1,m) cnt[i]+=cnt[i-1];
        DOR(i,n,1) sa[cnt[B[_sa[i]]]--]=_sa[i];
        rk[sa[1]]=1;
        FOR(i,2,n) rk[sa[i]]=rk[sa[i-1]]+(A[sa[i]]!=A[sa[i-1]] || B[sa[i]]!=B[sa[i-1]]);
    }
    FOR(i,1,n) {
        if(rk[i]==1) {h[rk[i]]=0;continue;}
        int l=max(0,h[rk[i-1]]-1),p=sa[rk[i]-1];
        for(; max(i,p)+l<=n && s[i+l]==s[p+l]; ++l);
        h[rk[i]]=l;
    }
}
char s[N];
int sa[N],rk[N],h0[N],h[21][N];
int n,K;
int qry(int u,int v) {
    if(u<1 || v>n) return 0;
    int p=rk[v],q=rk[n-u+1+n+1];
    if(p>q) swap(p,q);
    ++p;
    int k=__lg(q-p+1);
    return min(h[k][p],h[k][q-(1<<k)+1]);
}
void solve() {
    cin >> n >> K;
    cin >> s+1;
    s[n+1]='*';
    FOR(i,1,n) s[n+i+1]=s[n-i+1];
    build(s,n*2+1,sa,rk,h[0]);
    FOR(i,1,20) {
        FOR(j,1,n*2+1-(1<<i)+1) {
            h[i][j]=min(h[i-1][j],h[i-1][j+(1<<(i-1))]);
        }
    }
    int res=0;
    FOR(i,1,n) {
        int l=qry(i,i);
        int p=i-l,q=i+l;
        FOR(k,0,min(K,n-q+1)) {
            res=max(res,l*2-1+k*2+qry(p,q+k)*2);
        }
        FOR(k,0,min(K,p)) {
            res=max(res,l*2-1+k*2+qry(p-k,q)*2);
        }
    }
    FOR(i,1,n-1) {
        int l=qry(i,i+1);
        int p=i-l,q=i+1+l;
        FOR(k,0,min(K,n-q+1)) {
            res=max(res,l*2+k*2+qry(p,q+k)*2);
        }
        FOR(k,0,min(K,p)) {
            res=max(res,l*2+k*2+qry(p-k,q)*2);
        }
    }
    FOR(i,0,n) {
        FOR(j,i+1,min(n+1,i+K+1)) {
            res=max(res,j-i-1+K+qry(i,j)*2);
        }
    }
    cout << res << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}