#include<bits/stdc++.h>
using namespace std;
char ch[5000005];
int f[5000005];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;
    while(t--){
        int n,k;cin>>n>>k;
        ch[0]='#';ch[1]='$';
        for(int i=1;i<=n;i++){
            cin>>ch[2*i];
            ch[2*i+1]='$';
        }
        ch[2*n+2]='%';
        int mx=-1,y=-1;
        for(int i=1;i<=2*n+1;i++){
            f[i]=1;
            if(mx>=i)f[i]=min(f[2*y-i],mx-i+1);
            while(ch[i+f[i]]==ch[i-f[i]])f[i]++;
            if(mx<i+f[i]-1)mx=i+f[i]-1,y=i;
        }
        int ans=min(n+k,2*k);
        for(int i=1;i<=2*n+1;i++){
            int l=i-f[i]+1;
            int r=i+f[i]-1;
            l=(l+1)/2;
            r=(r-1)/2;
            if(l>r)continue;
            ans=max(ans,r-l+1+2*min(max(n-r,l-1),k));
        }
        cout<<ans<<endl;
    }
    return 0;
}