#include <bits/stdc++.h>

using namespace std;

mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());

int N, K;
string s;
long long sd[2];
long long pows[2][200005];
long long hsh[2][2][200005];
const long long MOD = 1e9+7;

long long mult(long long a, long long b) {
	return a * b % MOD;
}

long long sub(long long a, long long b) {
	return ((a - b) % MOD + MOD) % MOD;
}

long long add(long long a, long long b) {
	return (a + b) % MOD;
}

bool check(int i, int j, int l) {
	if (i < l || j < l) {
		return 0;
	}
	for (int k = 0; k < 2; k++) {
		if (sub(hsh[0][k][i], mult(hsh[0][k][i - l], pows[k][l])) 
		!= sub(hsh[1][k][j], mult(hsh[1][k][j - l], pows[k][l])) ) {
			return 0;
		}
	}
	return 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	sd[0] = 998244353;
	sd[1] = 500000001;
	pows[0][0] = pows[1][0] = 1;
	for (int i = 1; i <= 200000; i++) {
		pows[0][i] = mult(pows[0][i - 1], sd[0]);
		pows[1][i] = mult(pows[1][i - 1], sd[1]);
	}
    int T;
    cin >> T;
    while(T--) {
		cin >> N >> K;
		int ans = min(N, K + 1) + K;
		cin >> s;
		for (int t = 0; t < 2; t++) {
			for (int i = 1; i <= N; i++) {
				for (int k = 0; k < 2; k++) {
					hsh[t][k][i] = add(mult(hsh[t][k][i - 1], sd[k]), s[i - 1]);
				}
			}
			reverse(s.begin(), s.end());
		}
		vector<int> vec;
		for (int i = 1; i <= N; i++) {
			vec.push_back(i);
							// vec.emplace_back(make_pair(i, N - i + 1), -1);
			// if (i != N) {
			// 	vec.emplace_back(make_pair(i, N - i), -2);
			// }
		}
		for (int i = 1; i <= N; i++) {
			int l = 1, r = N;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (check(i, N - i + 1, mid)) {
					// cout << i << " " << mid << " " << 2 * mid - 1 + 2 * min(K, max(i - mid, N - (i + mid - 1))) << " " << i - mid << " " << N - (i + mid - 1) << endl;
					l = mid + 1;
					ans = max(ans, 2 * mid - 1 + 2 * min(K, max(i - mid, N - (i + mid - 1))));
				}
				else {
					r = mid - 1;
				}
			}
			if (i == N) {
				continue;
			}
			l = 1, r = N;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (check(i, N - (i + 1) + 1, mid)) {
					l = mid + 1;
					ans = max(ans, 2 * mid + 2 * min(K, max(i - mid, N - (i + mid))));
				}
				else {
					r = mid - 1;
				}
			}
		}
		shuffle(vec.begin(), vec.end(), rando);
		for (int i : vec) {
			for (int t = 0; t <= K + 1 && i + t + 1 <= N; t++) {
				int j = N - (i + t + 1) + 1;
				int c = t;
				if (!check(i, j, (ans - c - K) / 2 + 1)) {
					continue;
				}
				int l = (ans - c - K) / 2 + 1, r = min(i, j);
				while (l <= r) {
					int mid = (l + r) / 2;
					if (check(i, j, mid)) {
						ans = 2 * mid + c + K;
						l = mid + 1;
					}
					else {
						r = mid - 1;
					}
				}
			}
			
		}
		cout << ans << "\n";
    }

}