#include <bits/stdc++.h>
using namespace std;
#define lg(x) (31^__builtin_clz(x))
const int N=8e5+5;
int T,n,m,up,tp,ans,a[N],o[N],bc[N],sa[N],rk[N],mn[19][N];char a1[N];
void rSort()
{
	fill(bc,bc+up+1,0);for(int i=1;i<=n;++i) ++bc[rk[o[i]]];
	partial_sum(bc,bc+up+1,bc);for(int i=n;i;--i) sa[bc[rk[o[i]]]--]=o[i];
}
void build()
{
	up=300;copy(a+1,a+n+1,rk+1);iota(o+1,o+n+1,1);rSort();
	for(int l=1,t;l<=n;l*=2)
	{
		tp=0;for(int i=1;i<=l;++i) o[++tp]=n-i+1;
		for(int i=1;i<=n;++i) if(sa[i]>l) o[++tp]=sa[i]-l;
		rSort();for(int i=1;i<=n;++i) swap(rk[i],o[i]);t=rk[sa[1]]=1;
		for(int i=2;i<=n;++i)
			rk[sa[i]]=(o[sa[i]]==o[sa[i-1]] && o[sa[i]+l]==o[sa[i-1]+l])?t:++t;
		if(t==n) break;up=t;
	}
	for(int i=1,j,t=0;i<=n;++i) if(rk[i]>1)
	{
		j=sa[rk[i]-1];if(t) --t;
		while(i+t<=n && j+t<=n && a[i+t]==a[j+t]) ++t;mn[0][rk[i]]=t;
	}
	for(int i=1;(1<<i)<=n;++i) for(int j=1;j+(1<<i)-1<=n;++j)
		mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
}
int qry(int x,int y)
{
	if(x<1 || y>n) return 0;int t1=n-y+1;
	x=rk[n*2-x+1];y=rk[y];if(x>y) swap(x,y);++x;
	int t=lg(y-x+1);return min({mn[t][x],mn[t][y-(1<<t)+1],t1});
}
void slv()
{
	scanf("%d %d %s",&n,&m,a1+1);ans=0;
	for(int i=1;i<=n;++i) a[i]=a1[i],a[n+i]=a1[n-i+1];
	n*=2;build();n/=2;
	for(int i=1;i<=n;++i) for(int j=0;j<=m;++j)
		if(i+j-1<=n) ans=max(ans,j+m+qry(i-1,i+j)*2);
	for(int i=1,t;i<=n;++i)
	{
		t=qry(i,i);
		for(int j=0;j<=m;++j)
		{
			if(i+j+t-1<=n) ans=max(ans,(j+t+qry(i-t,i+j+t))*2-1);
			if(i-j-t+1>0) ans=max(ans,(j+t+qry(i-j-t,i+t))*2-1);
		}
	}
	for(int i=1,t;i<n;++i)
	{
		t=qry(i,i+1);
		for(int j=0;j<=m;++j)
		{
			if(i+j+t<=n) ans=max(ans,(j+t+qry(i-t,i+j+t+1))*2);
			if(i-j-t+1>0) ans=max(ans,(j+t+qry(i-j-t,i+t+1))*2);
		}
	}printf("%d\n",ans);
}
int main()
{
	scanf("%d",&T);
	while(T--) slv();return 0;
}