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

using ll = long long;
//#define int ll
#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()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back

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;
}

template<class T>
struct RMQ {
    vector<vector<T>> jmp;
    RMQ(){}
    RMQ(const vector<T>& 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]);
        }
    }
    T 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 SuffixArray {
    vi sa, lcp;
    vi rank;
    RMQ<int> rmq;
    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.resize(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++);

        rmq=RMQ(lcp);
//        for(int i=0;i<sz(sa);i++)
//            cout<<i<<" -> "<<sa[i]<<" "<<lcp[i]<<"\n";
    }
    int query(int i,int j)
    {
        i=rank[i],j=rank[j];
        if(i>j)
            swap(i,j);
        return rmq.query(i+1,j+1);
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        auto [even, odd] = manacher(s);
        string ss = s;
        reverse(all(ss));
        ss += "#" + s;
//        cout<<ss<<"\n";
        auto suf = SuffixArray(ss);
//        cout<<suf.query(18,7)<<"\n";
//        return 0;
        auto starts = [&](int i) { return n + 1 + i; };
        auto ends = [&](int i) { return n - 1 - i; };
        int ans = min(k+n,2*k);
        for (int i = 0; i < n; i++) {
            ans = max(ans, 2 * even[i] + k);
            ans = max(ans, 2 * odd[i] + 1 + k);
            for (auto [l, r]: {pii(i - 0, i + 0 - 1)})
                for (int m = 0; m <= k; m++)
                    for (auto [L, R]: {pii(l - m, r), pii(l, m + r)})
                        if (L >= 0 && R < n) {
                            ans = max(ans, suf.query(starts(R + 1), ends(L - 1)) * 2 + R - L + 1 + k);
//                            cout<<i<<" ["<<l<<","<<r<<"] "<<m<<" ["<<L<<","<<R<<"] ("<<starts(R + 1)<<","<<ends(L - 1)<<") -> "<<suf.query(starts(R + 1), ends(L - 1))<<" -> "<<suf.query(starts(R + 1), ends(L - 1)) * 2 + R - L + 1 + m<<"\n";
                        }
            for (auto [l, r]: {pii(i - even[i], i + even[i] - 1), pii(i - odd[i], i + odd[i])})
                for (int m = 0; m <= k; m++)
                    for (auto [L, R]: {pii(l - m, r), pii(l, m + r)})
                        if (L >= 0 && R < n) {
                            ans = max(ans, suf.query(starts(R + 1), ends(L - 1)) * 2 + R - L + 1 + m);
//                            cout<<i<<" ["<<l<<","<<r<<"] "<<m<<" ["<<L<<","<<R<<"] ("<<starts(R + 1)<<","<<ends(L - 1)<<") -> "<<suf.query(starts(R + 1), ends(L - 1))<<" -> "<<suf.query(starts(R + 1), ends(L - 1)) * 2 + R - L + 1 + m<<"\n";
                        }
        }
        cout<<ans<<"\n";
    }
}