#include <bits/stdc++.h>

using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif // LOCAL
const int inf=1e18;
const int p=1e9+7;
const int base=555;
const int maxn=5e5+5;
int h1[maxn];int h2[maxn];int po[maxn];
#define ha1 h1
#define ha2 h2
int n,k;
int get(int l,int r)
{
    return ((ha1[r]-po[r-l]*ha1[l])%p+p)%p;
}
int get2(int l,int r)
{
    return ((ha2[r]-po[r-l]*ha2[l])%p+p)%p;
}
int getrev(int l,int r)
{
    return get2(n-l,n-r);
}
bool check(int sl,int sr,int ans)
{
    if(sl+ans>n || sr-ans<0) return false;
    return get(sl,sl+ans)==getrev(sr,sr-ans);
}
string s;
int lcp(int sl,int sr)
{
    if(sl==n || sr==0 || s[sl]!=s[sr-1]) {return 0;}
    int ans=0;
    for(int i=19;i>=0;--i)
    {
        if(check(sl,sr,ans+(1<<i))) ans+=(1<<i);
    }
    return ans;
}
int res;
void upd(int sl,int sr)
{
    int sl1=sl;int sr1=sr;
    int ans=lcp(sl,sr);
    sr-=ans;sl+=ans;
    //debug(sl,sr,2*ans);
    for(int i=0;i<=k;++i)
    {
        if(sl+i<=n){
        res=max(res,(sl-sr)+2*i+2*lcp(sl+i,sr));
        }
    }
    for(int i=0;i<=k;++i)
    {
        if(sr-i>=0){
        res=max(res,(sl-sr)+2*i+2*lcp(sl,sr-i));
        }
    }
}
int sol(int n1,int k1,string s1)
{
    n=n1;k=k1;s=s1;
    for(int i=0;i<s.size();++i) {h1[i+1]=(h1[i]*base+s[i])%p;}
    reverse(all(s));
    for(int i=0;i<s.size();++i) {h2[i+1]=(h2[i]*base+s[i])%p;}
    reverse(all(s));
    res=min(2*k,n+k);
    for(int i=0;i<=n;++i)
    {
        for(int j=i;j<=i+k && j<=n;++j)
        {
            res=max(res,2*lcp(j,i)+(j-i)+k);
        }
    }
    for(int i=0;i<n;++i)
    {
        upd(i,i+1);
    }
    for(int i=0;i<=n;++i)
    {
        upd(i,i);
    }
    return res;
}
bool okk(string s)
{
    for(int i=0;i<s.size();++i)
    {
        if(s[i]!='?' && s[s.size()-i-1]!='?' && s[i]!=s[s.size()-i-1]) {return false;}
    }
    return true;
}
int st(string s)
{
    int answ=0;
    for(int l=0;l<s.size();++l)
    {
        for(int len=0;len<=s.size()-l;++len)
        {
            if(okk(s.substr(l,len))) {
                answ=max(answ,len);
            }
        }
    }
    return answ;
}
int stu(int n,int k,string s)
{
    int answ=0;
    for(int i=0;i<=n;++i)
    {
        string s1=s;
        for(int j=0;j<k;++j)
        {
            s1.insert(s1.begin()+i,'?');
        }
        answ=max(answ,st(s1));
    }
    return answ;
}
mt19937 rnd;
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    po[0]=1;for(int i=1;i<maxn;++i) {po[i]=(po[i-1]*base)%p;}
    #ifdef LOCAL
    int t;t=1e9;while(t--) {
    int n1,k1;string s1;n1=rnd()%10;k1=rnd()%10;for(int i=0;i<n1;++i) {s1.app(rnd()%2 ? 'a' : 'b');}
    int correct=stu(n1,k1,s1);int res=sol(n1,k1,s1);
    debug(n1,k1,s1);
    debug(correct,res);
    assert(correct==res);
    }
    #else
    int t;cin>>t;while(t--) {
    int n1,k1;string s1;cin>>n1>>k1>>s1;
    cout<<sol(n1,k1,s1)<<'\n';
    }
    #endif
    return 0;
}