#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const int p1=1e9+7,p2=1e9+9,N=3e5+10;
struct hsh{
	ll a,b;
	hsh (ll x=0,ll y=0){a=x,b=y;}
	hsh operator +(int c){return hsh((a+c)%p1,(b+c)%p2);}
}h1[N],h2[N],K[N];
bool operator ==(hsh a,hsh b){return a.a==b.a&&a.b==b.b;}
hsh operator -(hsh a,hsh b){return hsh((a.a-b.a+p1)%p1,(a.b-b.b+p2)%p2);}
hsh operator *(hsh a,hsh b){return hsh(a.a*b.a%p1,a.b*b.b%p2);}
int T,n,k,ans;
char str[N];
hsh calc1(int l,int r){return h1[r]-h1[l-1]*K[r-l+1];}
hsh calc2(int l,int r){return h2[l]-h2[r+1]*K[r-l+1];}
void work(int x,int y,int cur)
{
	ans=max(ans,cur);
	int p=(ans-cur)/2+1;
	if(x-p+1<1||y+p-1>n||!(calc1(x-p+1,x)==calc2(y,y+p-1))) return;
	int l=p+1,r=min(x,n-y+1)+1;
	while(l<r)
		if(calc1(x-mid+1,x)==calc2(y,y+mid-1)) l=mid+1;
		else r=mid;
	ans=max(ans,(l-1)*2+cur);
}
int main()
{
	scanf("%d",&T);
	K[0]=hsh(1,1),K[1]=hsh(131,131);
	for(int i=2;i<N;i++) K[i]=K[i-1]*K[1];
	while(T--)
	{
		scanf("%d%d%s",&n,&k,str+1);
		h1[0]=h2[n+1]=hsh(0,0),ans=k+min(n,k);
		for(int i=1;i<=n;i++) h1[i]=h1[i-1]*K[1]+str[i];
		for(int i=n;i;i--) h2[i]=h2[i+1]*K[1]+str[i];
		vector<pair<int,int>> v;
		vector<int> v1;
		for(int i=1;i<=n;i++)
		{
			int l=1,r=min(i,n-i+1);
			while(l<r)
				if(calc1(i-mid,i)==calc2(i,i+mid)) l=mid+1;
				else r=mid;
			ans=max(ans,2*l-1);
			v.push_back({i-l,i+l});
		}
		for(int i=1;i<n;i++)
		{
			int l=0,r=min(i,n-i);
			while(l<r)
				if(calc1(i-mid,i)==calc2(i+1,i+mid+1)) l=mid+1;
				else r=mid;
			ans=max(ans,l*2+k);
			v.push_back({i-l,i+l+1});
		}
		shuffle(v.begin(),v.end(),mt19937(0));
		for(auto x:v)
		{
			int len=x.second-x.first-1;
			for(int i=1;i<=k&&x.second+i<=n+1;i++) work(x.first,x.second+i,len+2*i);
			for(int i=1;i<=k&&x.first-i>=0;i++) work(x.first-i,x.second,len+2*i);
		}
		for(int i=1;i<=n;i++) v1.push_back(i);
		shuffle(v1.begin(),v1.end(),mt19937(0));
		for(auto x:v1)
			for(int i=1;i<=k&&x+i-1<=n;i++) work(x-1,x+i,k+i);
		printf("%d\n",ans);
	}
}