#include<bits/stdc++.h>
using namespace std;
char c[401000],c_[400100];
int p[401000],lg[401000];
namespace opj{
	int rk[1001000],sa[1010000],m,t[1001000],tr[1001000],h[401000],st[20][401000];
	void SA(int n){
		m=128;
		for(int i=1;i<=m;i++)t[i]=0;
		for(int i=1;i<=n;i++)t[rk[i]=c[i]]++;
		for(int i=1;i<=m;i++)t[i]+=t[i-1];
		for(int i=n;i;i--)sa[t[rk[i]]--]=i;
		for(int k=1;;k<<=1){
			int p=0;
			for(int i=n-k+1;i<=n;i++)tr[++p]=i;
			for(int i=1;i<=n;i++)if(sa[i]>k)tr[++p]=sa[i]-k;
			for(int i=1;i<=m;i++)t[i]=0;
			for(int i=1;i<=n;i++)t[rk[i]]++;
			for(int i=1;i<=m;i++)t[i]+=t[i-1];
			for(int i=n;i;i--)sa[t[rk[tr[i]]]--]=tr[i];
			for(int i=1;i<=n;i++)swap(tr[i],rk[i]);
			rk[sa[1]]=p=1;
			for(int i=2;i<=n;i++)rk[sa[i]]=(tr[sa[i-1]]==tr[sa[i]]&&tr[sa[i-1]+k]==tr[sa[i]+k])?p:++p;
			if(n==p)break;m=p;
		}
		for(int i=1,k=0;i<=n;i++){
			if(k)k--;int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&c[i+k]==c[j+k])k++;
			st[0][rk[i]]=k;
		}
		for(int j=1;j<20;j++)for(int i=1;i+(1<<j)-1<=n;i++)
			st[j][i]=min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
	}
	inline int lcp(int x,int y){
		x=rk[x],y=rk[y];if(x>y)swap(x,y);x++;
		int k=lg[y-x+1];
		return min(st[k][x],st[k][y-(1<<k)+1]);
	}
}
int n,m;
int sol(){
	for(int i=1;i<=n;i++)c[n*2+1-i]=c[i];
	opj::SA(n*2);
	c_[0]='?',c_[1]='#';
	for(int i=1;i<=n;i++)c_[i*2]=c[i],c_[i*2+1]='#';
	c_[n*2+2]='!';
	for(int i=0;i<=n*2+2;i++)p[i]=0;
	int ans=m+min(n,m);
	for(int i=1,mx=0,id=0;i<=n*2+1;i++){
		if(i<=mx)p[i]=min(mx-i+1,p[2*id-i]);
		while(c_[i+p[i]]==c_[i-p[i]])p[i]++;
		if(i+p[i]-1>mx)mx=i+p[i]-1,id=i;
		ans=max(ans,p[i]-1);
		if(!(i&1)){
			int e=p[i]/2,L=i/2-e,R=i/2+e;
			for(int j=1;j<=m&&R+j<=n+1;j++){
				int lc=0;
				if(L&&R+j<=n)lc=min(opj::lcp(R+j,n*2+1-L),n+1-(R+j));
				ans=max(ans,p[i]-1+(lc+j)*2);
			}
			for(int j=1;j<=m&&j<=L;j++){
				int lc=0;
				if(j<L&&R<=n)lc=min(opj::lcp(R,n*2+1-(L-j)),n+1-R);
				ans=max(ans,p[i]-1+(lc+j)*2);
			}
		}
		else{
			int e=p[i]/2,L=i/2-e,R=(i+1)/2+e;
			for(int j=1;j<=m&&R+j<=n+1;j++){
				int lc=0;
				if(L&&R+j<=n)lc=min(opj::lcp(R+j,n*2+1-L),n+1-(R+j));
				ans=max(ans,p[i]-1+(lc+j)*2);
			}
			for(int j=1;j<=m&&j<=L;j++){
				int lc=0;
				if(j<L&&R<=n)lc=min(opj::lcp(R,n*2+1-(L-j)),n+1-R);
				ans=max(ans,p[i]-1+(lc+j)*2);
			}
		}
	}
	return ans;
}
void soll(){
	scanf("%d%d%s",&n,&m,c+1);
	int ans=sol();
	for(int i=2;i<=n;i++)for(int j=i;j<n&&j-i+1<=m;j++)
	ans=max(ans,min(opj::lcp(j+1,n*2+2-i),n-j)*2+j-i+1+m);
	printf("%d\n",ans);
}
int main(){
	lg[0]=-1;
	for(int i=1;i<=400000;i++)lg[i]=lg[i>>1]+1;
	int T;scanf("%d",&T);while(T--)soll();
	return 0;
}