#include <bits/stdc++.h>
#define int unsigned long long
#define double long double
using namespace std;
const int mul=131;
int prehsh[1000005],sufhsh[1000005],pw[1000005],n;
string s;
bool comp(int l1,int r1,int l2,int r2){
	if((prehsh[r1]-prehsh[l1-1])*pw[1000000-l1]==(sufhsh[l2]-sufhsh[r2+1])*pw[1000000-(n-r2+1)]) return true;
	return false;
}
int findlongest(int sl,int sr){
	if(sl==0||sr==n+1) return 0;
	if(s[sl]!=s[sr]) return 0;
	int l=1,r=min(sl,n-sr+1);
	while(l<r){
		int mid=(l+r+1)>>1;
		if(comp(sl-mid+1,sl,sr,sr+mid-1)) l=mid;
		else r=mid-1;
	}
	return l;
}
signed main(){
	pw[0]=1; for(int i=1;i<=1000000;i++) pw[i]=pw[i-1]*mul;
	int t; cin>>t;
	while(t--){
		int k,ans=0; cin>>n>>k;
		cin>>s; s=" "+s;
		if(k>=n){
			cout<<n+k<<"\n";
			continue;
		}
		prehsh[0]=0,sufhsh[n+1]=0;
		for(int i=1;i<=n;i++) prehsh[i]=(prehsh[i-1]+pw[i]*s[i]);
		for(int i=n;i>=1;i--) sufhsh[i]=(sufhsh[i+1]+pw[n-i+1]*s[i]);
		for(int i=1;i<=k;i++){
			for(int j=1;j+i-1<=n;j++){
				ans=max(ans,findlongest(j-1,j+i)*2+i+k);
			}
		}
		for(int i=1;i<=n;i++){
			int p=findlongest(i-1,i+1);
			int nl=i-p-1,nr=i+p+1;
			ans=max(ans,p*2+1);
			for(int j=1;j<=k;j++){
				if(nl>=j){
					ans=max(ans,findlongest(nl-j,nr)*2+j*2+p*2+1);
				}
				if(nr<=n-j+1){
					ans=max(ans,findlongest(nl,nr+j)*2+j*2+p*2+1);
				}
			}
		}
		for(int i=1;i<n;i++){
			int p=findlongest(i,i+1);
			int nl=i-p,nr=i+p+1;
			ans=max(ans,p*2);
			for(int j=1;j<=k;j++){
				if(nl>=j){
					ans=max(ans,findlongest(nl-j,nr)*2+j*2+p*2);
				}
				if(nr<=n-j+1){
					ans=max(ans,findlongest(nl,nr+j)*2+j*2+p*2);
				}
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}