#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define all(p) p.begin(),p.end()
using ll =long long;

struct RH{
    using u64=uint64_t;
    static inline const u64 mod = 0x1FFF'FFFF'FFFF'FFFF,base=mt19937_64 {random_device{}()}()%mod;
    ll n;
    vector<u64> hash,pow;
    static u64 add(u64 a,u64 b){
        a+=b;
        if(a>=mod) a-=mod;
        return a;
    }
    static u64 mul(u64 a,u64 b){
        auto c=__uint128_t(a)*b;
        return add(c>>61,c&mod);
    }
    RH(const string &s):n(s.size()),hash(n+1),pow(n+1,1){
        for(ll i = 0;i<n;i++){
            pow[i+1]=mul(pow[i],base);
            hash[i+1]=add(mul(hash[i],base),s[i]);
        }
    }
    u64 get(ll l,ll r) const {
        return add(hash[r],mod-mul(hash[l],pow[r-l]));
    }
};

void solve(){
    int N,K;
    cin>>N>>K;
    string S;
    cin>>S;
    int ans=0;
    string T=S;
    reverse(all(T));
    RH A(S),B(T);
    auto f=[&](int l,int r) -> int {
        int ml=0,mr=1+min(l,N-r);
        while(mr-ml>1){
            int m=(ml+mr)/2;
            if(A.get(l-m,l)==B.get(N-(r+m),N-r)){
                ml=m;
            }
            else{
                mr=m;
            }
        }
        return ml;
    };
    rep(l,-K,N) rep(len,K-1,K+1){
        int L=max(l,0),R=min(l+len,N);
        if(R<0) continue;
        ans=max(ans,K+R-L+f(L,R)*2);
    }
    rep(l,0,N+1) rep(r,l,l+2){
        if(r>N) continue;
        int tmp=f(l,r);
        int L=l-tmp,R=r+tmp;
        rep(c,0,K+1){
            if(L>=c){
                ans=max(ans,R-L+2*(c+f(L-c,R)));
            }
            if(R+c<=N){
                ans=max(ans,R-L+2*(c+f(L,R+c)));
            }
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}
/*
4
1 3
a
4 1
icpc
4 2
icpc
8 4
icecream

*/