#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=400005,K=20;
int lg[N];
struct SA{
	char s[N];
	int n,m;
	int sa[N],rk[N],tmp[N],h[N],bin[N],f[N][K];
	void radixSort(){
		rep(i,0,m)bin[i]=0;
		rep(i,1,n)++bin[rk[i]];
		rep(i,1,m)bin[i]+=bin[i-1];
		per(i,n,1)sa[bin[rk[tmp[i]]]--]=tmp[i];
	}
	void getSa(){
		rep(i,1,n)rk[i]=s[i],tmp[i]=i;
		radixSort();
		for(int l=1,p=0;p<n;m=p,l<<=1){
			p=0;
			rep(i,n-l+1,n)tmp[++p]=i;
			rep(i,1,n)if(sa[i]>l)tmp[++p]=sa[i]-l;
			radixSort();
			rep(i,1,n)swap(rk[i],tmp[i]);
			rk[sa[1]]=p=1;
			rep(i,2,n){
				int k1=sa[i-1]+l<=n?tmp[sa[i-1]+l]:0;
				int k2=sa[i  ]+l<=n?tmp[sa[i  ]+l]:0;
				rk[sa[i]]=(tmp[sa[i-1]]==tmp[sa[i]]&&k1==k2?p:++p);
			}
		}
	}
	void getHeight(){
		int k=0;
		rep(i,1,n){
			if(k)--k;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
			h[rk[i]]=k;
		}
		rep(i,1,n)f[i][0]=h[i];
		rep(j,1,K-1)rep(i,1,n-(1<<j)+1)f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
	void init(char *t){
		n=strlen(t+1);
		rep(i,1,n)s[i]=t[i];
		m=256;
		getSa();
		getHeight();
	}
	int ask(int l,int r){
		int x=lg[r-l+1];
		return min(f[l][x],f[r-(1<<x)+1][x]);
	}
	int LCP(int k1,int k2){
		if(k1<0||k2<0||k1>n||k2>n)return 0;
		k1=rk[k1],k2=rk[k2];
		if(k1>k2)swap(k1,k2);
		if(k1==k2)return n-sa[k1]+1;
		else return ask(k1+1,k2);
	}
}A;
int T,n,k;
char s[N],s0[N];
int h[N];
int query(int a,int b){
	if(a<1||b>n)return 0;
	return min({a,n+1-b,A.LCP(n+a,b)});
}
signed main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rep(i,2,N-1)lg[i]=lg[i>>1]+1;
	cin>>T;
	while(T--){
		scanf("%d%d",&n,&k);
		scanf("%s",s+1);
		rep(i,1,n){
			s[n+i]=s[n+1-i];
		}
		s[n+n+1]=0;
		A.init(s);
		rep(i,1,n)s0[i]=s[i];
		s[0]='#';
		int m=0;
		rep(i,1,n){
			s[++m]='$';
			s[++m]=s0[i];
		}
		s[++m]='$';
		s[m+1]='!';
		
		int ans=k+min(n,k+1);
		
		int max_r=0,pos=0;
		rep(i,1,m){
			if(max_r>i){
				h[i]=min(max_r-i,h[pos*2-i]);
			}else{
				h[i]=1;
			}
			while(s[i-h[i]]==s[i+h[i]])++h[i];
			if(i+h[i]>max_r){
				max_r=i+h[i];
				pos=i;
			}
			ans=max(ans,h[i]-1);
			if(i&1){
				ans=max(ans,h[i]-1+k);
			}
		}
		rep(i,1,m){
			int l=(i-h[i])/2+1;
			int r=(i+h[i])/2-1;
			rep(_,1,k){
				if(r+_<=n){
					ans=max(ans,h[i]-1+query(l-1,r+_+1)+_*2);
				}
				if(l-_>=1){
					ans=max(ans,h[i]-1+query(l-_-1,r+1)+_*2);
				}
			}
		}
		
		printf("%d\n",ans);
	}
	return 0;
}

/*

(gdb) p *h@20
$1 = {0, 1, 2, 1, 2, 1, 4, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
(gdb) p *s@20
$2 = "#$i$c$p$c$!\000\000\000\000\000\000\000\000
*/