#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <assert.h>
#include <math.h>
#include <set>
#include <vector>
using std::min;
#define od(x) printf("%lld",x)
#define odb(x) printf("%lld ",x)
#define odl(x) printf("%lld\n",x)
#define odp(x,y) printf("%lld %lld\n",x,y)
using pi=std::pair<int,int>;
using vi=std::vector<int>;
using vpi=std::vector<pi>;
const int mod=998244353;
#define x first
#define y second
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
inline int read()
{
	int num=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>47&&c<58)num=num*10+(c^48),c=getchar();
	return num*f;
}
void mae(int &x,int y){x=x+y;if(x>=mod)x-=mod;}
int me(int x,int y){return x*y%mod;}
void mxe(int &a,int b){if(a<b)a=b;}
int sa[1234567],rk[1234567];
pi tmp[1234567],vv[1234567];
int sz[1234567],tk[1234567],od[1234567],pk[1234567],height[1234567];
char a[1234567];
vpi g[1234567];
void SA(char *t,int n)
{
	for(int i=1;i<=max(n*2,1000);i++)
		sa[i]=rk[i]=tmp[i].first=tmp[i].second=vv[i].first=vv[i].second
		=sz[i]=tk[i]=od[i]=pk[i]=height[i]=0;
	for(int i=1;i<=n;i++)t[i]-=96;
	memset(rk,0,sizeof(rk));
	for(int i=1;i<=n;i++)rk[i]=t[i];
	int Q=std::max(n,200);
	for(int j=1;j<=n;j<<=1)
	{
		//sort by 2k
		for(int i=0;i<=Q;i++)sz[i]=0;
		for(int i=1;i<=n;i++)sz[rk[j+i]+1]++;
		for(int i=1;i<=Q;i++)sz[i]+=sz[i-1];
		for(int i=1;i<=n;i++)tk[++sz[rk[j+i]]]=i;
		//sort by 1k
		for(int i=0;i<=Q;i++)sz[i]=0;
		for(int i=1;i<=n;i++)sz[rk[i]+1]++;
		for(int i=1;i<=Q;i++)sz[i]+=sz[i-1];
		for(int i=1;i<=n;i++)od[++sz[rk[tk[i]]]]=tk[i];
		for(int i=1;i<=n;i++)
		{
			int x=od[i],y=od[i-1];
			if(i==1||rk[x]!=rk[y]||rk[x+j]!=rk[y+j])pk[i]=1;
			else pk[i]=0;
		}
		for(int i=1;i<=n;i++)rk[od[i]]=rk[od[i-1]]+pk[i];
	}
	for(int i=1;i<=n;i++)sa[rk[i]]=i;
	for(int i=0,k=0;i<n;i++)
	{
		if(rk[i]==0)continue;
		if(k)k--;
		int j=sa[rk[i]-1];
		while(j+k<=n&&i+k<=n&&t[i+k]==t[j+k])k++;
		height[rk[i]]=k;
		if(i&&j)g[k].push_back({i,j});
	}
}
#define sz szsz
#define mgs int fa[1<<22],sz[1<<22];\
inline int f(int x){return x==fa[x]?x:fa[x]=f(fa[x]);}\
inline int uf(int x,int y)\
{\
    int fx=f(x),fy=f(y);\
    if(fx==fy)return 0;\
    if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;\
    fa[fx]=fy,sz[fy]+=sz[fx];\
    return 1;\
}

mgs
struct STmin{
	int a[21][1000005],n;
	void build(int N,int *b)
	{
		n=N;
		for(int i=1;i<=n;i++)a[0][i]=b[i];
		for(int i=1;i<=20;i++)
			for(int j=1;j<=n-(1<<i)+1;j++)
				a[i][j]=min(a[i-1][j],a[i-1][j+(1<<i-1)]);
	}
	int q(int l,int r)
	{
		int d=std::__lg(r-l+1);
		return min(a[d][l],a[d][r-(1<<d)+1]);
	}
};
STmin st;

int lcp(int l,int r)
{
	if(l==r)return 1145141;
	l=rk[l],r=rk[r];
	if(l>r)std::swap(l,r);
	return st.q(l+1,r);
}
int n,k;
int get(int x,int y){
	if(x<1||x>n||y<1||y>n)return 0;
	int mx=min(n-x+1,y);
	return min(lcp(x,2*n+1-y),mx);
}
int L[400005][2],R[400005][2];
signed main()
{
	int T=read();while(T--){
	
		n=read(),k=read();
		scanf("%s",a+1);
		for(int i=1;i<=n;i++)a[n+n+1-i]=a[i];
		// puts(a+1);
		SA(a,n+n);
		st.build(n+n,height);
		// printf("lcp=%d\n",lcp(3,6));
		// for(int i=1;i<=n*2;i++)printf("%d ",rk[i]);puts("");
		// for(int i=1;i<=n*2;i++)printf("%d ",height[i]);puts("");
		for(int i=2;i<=2*n;i++)
			for(int j=0;j<=1;j++)
			{
				if(i%2==0)L[i][j]=R[i][j]=i/2;
				else L[i][j]=i/2+1,R[i][j]=i/2;
			}
		int res=0;
		for(int j=0;j<=0;j++)
			for(int i=2;i<=n*2;i++)
			{
				int len=get(R[i][j]+1,L[i][j]-1);
				L[i][j]-=len,R[i][j]+=len;
				// printf("%d %d : [%d %d]\n",i,j,L[i][j],R[i][j]);
				int _=i;
				if(j==0)
				{
					for(int z=1;z<=k;z++)
					{
						int l=L[i][j],r=R[i][j]+z;
						if(r<=n)
						{
							res=max(res,r-l+1+z+get(r+1,l-1));
							// if(r-l+1+i+get(r+1,l-1)==13)
							// {
								// printf("_,i=%d %d l,r=%d %d\n",_,i,l,r);
							// }
							// L[l+r][j+1]=min(L[l+r][j+1],l);
							// R[l+r][j+1]=max(R[l+r][j+1],r);
						}
						l=L[i][j]-z,r=R[i][j];
						if(l>=1)
						{
							res=max(res,r-l+1+z+get(r+1,l-1));
							// L[l+r][j+1]=min(L[l+r][j+1],l);
							// R[l+r][j+1]=max(R[l+r][j+1],r);
						}
					}
				}
				// if(R[i][j]!=n)
				// {
					// int l=L[i][j],r=R[i][j]+1;
					// L[l+r][j+1]=min(L[l+r][j+1],l);
					// R[l+r][j+1]=max(R[l+r][j+1],r);
				// }
				// if(L[i][j]!=1)
				// {
					// int l=L[i][j]-1,r=R[i][j];
					// L[l+r][j+1]=min(L[l+r][j+1],l);
					// R[l+r][j+1]=max(R[l+r][j+1],r);
				// }
				res=max(res,R[i][j]-L[i][j]+1+k);
			}
		for(int z=1;z<=k;z++)
		{
			for(int l=1,r=z;r<=n;l++,r++)
			{
				res=max(res,z+k+2*get(r+1,l-1));
				// printf("[%d %d]:%d\n",l,r,z+k+2*get(r,l));
			}
		}
		printf("%d\n",res);
	}
}