#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;

const int maxn = 410000;
const int maxd = 20;

namespace Suffix_Array
{
	int t[maxn];
	void sort_(int str[],int sa[],int rk[],int n,int m)
	{
		for(int i=0;i<=m;i++) t[i]=0;
		for(int i=1;i<=n;i++) t[str[sa[i]]]++;
		for(int i=1;i<=m;i++) t[i]+=t[i-1];
		for(int i=n;i>=1;i--) rk[ t[str[sa[i]]]-- ]=sa[i];
	}
	int n;
	int str[maxn];
	int sa[maxn],rank[maxn],fir[maxn],sec[maxn];
	void get_SA()
	{
		for(int i=1;i<=n;i++) rank[i]=i;
		sort_(str,rank,sa,n,30);
		rank[sa[1]]=1;
		for(int i=2;i<=n;i++) rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
		int h=1;
		while(rank[sa[n]]!=n)
		{
			for(int i=1;i<=n;i++)
			{
				fir[i]= rank[i], sec[i]= i+h>n ? 0 : rank[i+h];
				sa[i]=i;
			}
			sort_(sec,sa,rank,n,n);
			sort_(fir,rank,sa,n,n);
			rank[sa[1]]=1;
			for(int i=2;i<=n;i++) rank[sa[i]] = rank[sa[i-1]] + (fir[sa[i]]!=fir[sa[i-1]] || sec[sa[i]]!=sec[sa[i-1]]);
			h<<=1;
		}
	}
	int height[maxn];
	void get_Height()
	{
		height[1]=0; int k=0;
		for(int i=1;i<=n;i++)
		{
			if(k) k--;
			if(rank[i]==1) continue;
			while( str[i+k] == str[sa[rank[i]-1]+k] ) k++;
			height[rank[i]]=k;
		}
	}
	int f[maxd][maxn];
	void build_rmq()
	{
		for(int i=1;i<=n;i++)
		{
			f[0][i]=height[i];
		}
		for(int d=1;(1<<d)<=n;d++)
		{
			for(int i=1;i+(1<<d)-1<=n;i++)
			{
				f[d][i]=min( f[d-1][i], f[d-1][i+(1<<(d-1))] );
			}
		}
	}
	int query(int l,int r)
	{
		if(l==r) return n-l+1;
		
		l=rank[l],r=rank[r];
		if(l>r) swap(l,r);
		l++;
		
		int len=r-l+1;
		int d= 31-__builtin_clz(len);
		
		return min(f[d][l],f[d][r-(1<<d)+1]);
	}
	void main(string S) //  S-'z'+1-Sr    1-based
	{
		n=S.size();
		for(int i=1;i<=n;i++) str[i]= S[i]-'a'+1;
		str[n+1]=-1;
		get_SA();
		get_Height();
		build_rmq();
	}
}

int n,K;
int query(int l,int r){
	if (l<1 || r>n) return 0;
	return Suffix_Array::query(r,2*n+2-l);
}

signed main()
{
	/////////////////////////////////////////////////
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
//	Suffix_Array::main(" asbcsba");
//	cout << "test :" << Suffix_Array::query(1,4) << endl;
	
	int Tcase=1; cin>>Tcase;
	while(Tcase--)
	{
		cin >> n >> K;
		string s;
		cin >> s;
		
		s=" "+s;
		{
			string tmp;
			for (auto x:s) tmp.push_back(x);
			tmp.push_back('z'+1);
			for (int i=n;i>=0;i--) tmp.push_back(s[i]);
			Suffix_Array::main(tmp);
//			cerr << "+";
//			cerr << tmp;
//			cerr << "+";
//			cerr << endl;
		}
		int ans=K;
		for (int i=1;i<=n;i++){
			for (int j=i-1;j<=i+K-1 && j<=n;j++){
				int tmp=query(i-1,j+1);
			//	cerr << "i,j,tmp : " << i-1 << " " << j+1 << " " << tmp << endl;
				ans=max(ans,(tmp*2)+(j-i+1)+K);
			}
		}
	//	cerr << ans << endl;
		for (int i=1;i<=n;i++){
			int len=query(i,i);
			int l=i-len;
			int r=i+len;
			ans=max(ans,2*len-1+K);
			for (int R=r;R<=r+K-1 && R<=n;R++){
				int tmp=query(l,R+1);
			//	cerr << "i,l,r,R,tmp : " << i << " " << l << " " << r << " " << R << " " << tmp << endl;
				ans=max(ans,(2*len-1)+2*(R-r+1)+(tmp*2));	
			}
			for (int L=l;L>=l-K+1 && L>=1;L--){
				int tmp=query(L-1,r);
				ans=max(ans,(2*len-1)+2*(l-L+1)+(tmp*2));	
			}
		}
		for (int i=1;i<n;i++){
			int len=query(i,i+1);
			int l=i-len;
			int r=i+1+len;
			ans=max(ans,2*len+K);
			for (int R=r;R<=r+K-1 && R<=n;R++){
				int tmp=query(l,R+1);
				ans=max(ans,(2*len)+2*(R-r+1)+(tmp*2));	
			}
			for (int L=l;L>=l-K+1 && L>=1;L--){
				int tmp=query(L-1,r);
				ans=max(ans,(2*len)+2*(l-L+1)+(tmp*2));	
			}
		}
		cout << ans << "\n";
	}
	return 0;
}