#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;

struct SuffixArray {
	vi sa, lcp;
	SuffixArray() {}
	SuffixArray(string& s, int lim=256) { // or basic_string<int>
		int n = sz(s) + 1, k = 0, a, b;
		vi x(all(s)+1), y(n), ws(max(n, lim)), rank(n);
		sa = lcp = 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,1,n) rank[sa[i]] = i;
		for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for (k && k--, j = sa[rank[i] - 1];
					s[i + k] == s[j + k]; k++);
	}
};

struct RMQ {
	vector<vector<int>> jmp;
	RMQ(const vector<int>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
			jmp.emplace_back(sz(V) - pw * 2 + 1);
			rep(j,0,sz(jmp[k]))
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	RMQ() {}
	int query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

struct PalRev {
	int n; string t;
	SuffixArray SA;
	RMQ rmq;
	vector<int> sa_id;

	PalRev(string s) {
		n = s.size();
		t = s;
		t += "#";
		reverse(s.begin(), s.end());
		t += s;
		SA = SuffixArray(t);
		rmq = RMQ(SA.lcp);

		sa_id.resize(SA.sa.size());
		for (int i = 0; i < sa_id.size(); i++) {
			sa_id[SA.sa[i]] = i;
		}
	}

	int getMxLen(int a, int b) { // if [a, b) were removed, what's the maximum palindrome centered at removal point
		// abcdef
		// fedcba
		// remove [2, 5)
		// lcp of [5] 1st string
		// vs [4] 2nd string
		int id1 = b;
		int id2 = n-a;

		int l = sa_id[id1];
		int r = sa_id[id2+n+1];
		if (l > r) swap(l, r);
		return rmq.query(l+1, r+1); 
	}
};

array<vi, 2> manacher(const string& s) {
	int n = sz(s);
	array<vi,2> p = {vi(n+1), vi(n)};
	rep(z,0,2) for (int i=0,l=0,r=0; i < n; i++) {
		int t = r-i+!z;
		if (i<r) p[z][i] = min(t, p[z][l+t]);
		int L = i-p[z][i], R = i+p[z][i]-!z;
		while (L>=1 && R+1<n && s[L-1] == s[R+1])
			p[z][i]++, L--, R++;
		if (R>r) l=L, r=R;
	}
	return p;
}

void solve() {
	int n, k; cin >> n >> k;
	string s; cin >> s;

	auto pls = manacher(s);
	PalRev hrv(s);

	int ans = 0;
	for (int p = 0; p < 2; p++) {
		for (int i = 0; i < pls[p].size(); i++) {
			int pallen = pls[p][i]*2 + p;
			int lp = i - pls[p][i];
			int rp = lp + pallen;
			ans = max(ans, pallen + k);

			for (int offset = 0; offset <= k; offset++) {
				int lpal = lp-offset;
				int rpal = rp;

				if (lpal < 0) break;
				int len = hrv.getMxLen(lpal, rpal);
				ans = max(ans, pallen + offset*2 + len*2);
			}

			for (int offset = 0; offset <= k; offset++) {
				int lpal = lp;
				int rpal = rp+offset;

				if (rpal > n) break;
				int len = hrv.getMxLen(lpal, rpal);
				ans = max(ans, pallen + offset*2 + len*2);
			}
		}
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t; cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}