#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 H {
	typedef uint64_t ull;
	ull x; H(ull x=0) : x(x) {}
#define OP(O,A,B) H operator O(H o) { ull r = x; asm \
	(A "addq %%rdx, %0\n adcq $0,%0" : "+a"(r) : B); return r; }
	OP(+,,"d"(o.x)) OP(*,"mul %1\n", "r"(o.x) : "rdx")
	H operator-(H o) { return *this + ~o.x; }
	ull get() const { return x + !~x; }
	bool operator==(H o) const { return get() == o.get(); }
	bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11+3; // (order ~ 3e9; random also ok)

struct HashInterval {
	vector<H> ha, pw;
	HashInterval(string& str) : ha(sz(str)+1), pw(ha) {
		pw[0] = 1;
		rep(i,0,sz(str))
			ha[i+1] = ha[i] * C + str[i],
			pw[i+1] = pw[i] * C;
	}
	HashInterval() {}

	H hashInterval(int a, int b) { // hash [a, b)
		return ha[b] - ha[a] * pw[b - a];
	}
};

H hashString(string& s){H h{}; for(char c:s) h=h*C+c;return h;}

struct HashRev {
	HashInterval hs, hsrev;
	int n;

	HashRev(string s) {
		n = s.size();
		hs = HashInterval(s);
		reverse(s.begin(), s.end());
		hsrev = HashInterval(s);
	}

	H hashInterval(int a, int b) { // hash [a, b)
		return hs.hashInterval(a, b);
	}

	H hashReverse(int a, int b) { // hash reverse [a, b)
		return hsrev.hashInterval(n-b, n-a);
	}
};

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);
	HashRev 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);

			//cout << p << ' ' << i << ' ' << lp << ' ' << rp << '\n';

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

				if (lpal < 0) break;

				int lo = 0, hi = min(lpal, n-rpal);
				while (lo < hi) {
					int mid = (lo+hi+1)/2;

					H hs1 = hrv.hashInterval(rpal, rpal+mid);
					H hs2 = hrv.hashReverse(lpal-mid, lpal);

					if (hs1 == hs2) {
						lo = mid;
					} else {
						hi = mid-1;
					}
				}
				ans = max(ans, pallen + offset*2 + lo*2);
				//cout << "OFFSET L " << offset << ' ' << lo << ' ' << pallen + offset*2 + lo*2 << '\n';
			}

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

				if (rpal > n) break;

				int lo = 0, hi = min(lpal, n-rpal);
				while (lo < hi) {
					int mid = (lo+hi+1)/2;

					H hs1 = hrv.hashInterval(rpal, rpal+mid);
					H hs2 = hrv.hashReverse(lpal-mid, lpal);

					if (hs1 == hs2) {
						lo = mid;
					} else {
						hi = mid-1;
					}
				}
				ans = max(ans, pallen + offset*2 + lo*2);
				//cout << "OFFSET R " << offset << ' ' << lo << ' ' << pallen + offset*2 + lo*2 << '\n';
			}
		}
	}
	cout << ans << '\n';
}

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