#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
#define rep(i,a,b) for (int i=a;i<(b);++i)
#define sz(a) (int)(a).size()

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

struct rmq {
	vi mins[20];
	rmq(vi v={})
	{
		if (v.empty()) return;
		int n=v.size();
		for (int i=0;i<20;++i) mins[i]=vi(n);
		for (int i=0;i<n;++i) mins[0][i]=v[i];
		for (int j=0;j<18;++j) for (int i=0;i<n-(1<<j);++i) mins[j+1][i]=min(mins[j][i],mins[j][i+(1<<j)]);
	}
	int ge(int l,int r)
	{
		assert(r>l);
		int dis=__lg(r-l);
		return min(mins[dis][l],mins[dis][r-(1<<dis)]);
	}
};

struct SA {
	vi sa,lc,rank;
	rmq rm;
	SA(const string&s,int lim=256)
	{
		int n=sz(s)+1,k=0,a,b;
		vi x(all(s)+1),y(n),ws(max(n,lim));
		rank=vi(n);
		sa=lc=y,iota(all(sa),0);
		for (int j=0,p=0;p<n;j=max(1,j*2),lim=p) {
			p=j,iota(all(y),n-j);
			rep(i,0,n) if (sa[i]>=j) y[p++]=sa[i]-j;
			fill(all(ws),0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i]+=ws[i-1];
			for (int i=n;i--;) sa[--ws[x[y[i]]]]=y[i];
			swap(x,y),p=1,x[sa[0]]=0;
			rep(i,1,n) a=sa[i-1],b=sa[i],x[b]=(y[a]==y[b] && y[a+j]==y[b+j]) ? p-1 : p++;
		}
		rep(i,0,n) rank[sa[i]]=i;
		for (int i=0,j;i<n-1;lc[rank[i++]]=k)
			for (k && k--,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
		rm=rmq(lc);
	}
	int lcp(int i,int j)
	{
		int p1=rank[i],p2=rank[j];
		if (p1==0 || p2==0) return 0;
		if (p2<p1) swap(p1,p2);
		return rm.ge(p1+1,p2+1);
	}
};

int t,n,k;

int solve(string s)
{
	string re=s;
	reverse(all(re));
	string u=s+"#"+re;
	SA suf(u);
	int an=k+min(n,k);
	for (int cen=0;cen<n;++cen)
	{
		int pallen=suf.lcp(cen,2*n-cen);
		int l=cen-pallen+1,r=cen+pallen-1;
		an=max(an,pallen*2-1+min(k,max(l,n-r-1))*2);
		for (int nak=1;nak<=min(k,l);++nak)
		{
			int ko=suf.lcp(r+1,2*n-(l-nak-1));
			an=max(an,pallen*2-1+(nak+ko)*2);
		}
	}
	for (int cen=1;cen<n;++cen)
	{
		int pallen=suf.lcp(cen,2*n-(cen-1));
		//if (pallen==0) continue;
		int l=cen-pallen,r=cen+pallen-1;
		an=max(an,pallen*2+min(k,max(l,n-r-1))*2);
		for (int nak=1;nak<=min(k,l);++nak)
		{
			int ko=suf.lcp(r+1,2*n-(l-nak-1));
			//cout<<cen<<' '<<l<<' '<<r<<' '<<pallen<<' '<<nak<<' '<<ko<<en;
			an=max(an,pallen*2+(nak+ko)*2);
		}
	}
	return an;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>n>>k;
		string s;
		cin>>s;
		int od=solve(s);
		reverse(all(s));
		od=max(od,solve(s));
		cout<<od<<en;
	}
}