#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MAXN = 400200;
const int K = 19;

int lg[MAXN];

struct SuffMass {
    vector<int> table[K];
    vector<int> order;
    vector<int> lcp;
    vector<int> id;
    SuffMass(string s) {
        s += '$';
        int n = s.size();
        order.resize(n);
        vector<int> classes(n);
        vector<int> new_order(n);
        vector<int> new_classes(n);
        vector<int> cnt(n);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {
            return s[a] < s[b];
        });
        classes[order[0]] = 0;
        for (int i = 1; i < n; ++i)
            classes[order[i]] = classes[order[i - 1]] + (s[order[i]] != s[order[i - 1]]);
        auto safe = [&](int x) {
            if (x >= n)
                return x - n;
            return x;
        };
        for (int l = 1; l < n; l *= 2) {
            fill(cnt.begin(), cnt.end(), 0);
            for (int i = 0; i < n; ++i)
                ++cnt[classes[i]];
            for (int i = 1; i < n; ++i)
                cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; --i) {
                int j = order[i] - l;
                if (j < 0)
                    j += n;
                --cnt[classes[j]];
                new_order[cnt[classes[j]]] = j;
            }
            new_classes[new_order[0]] = 0;
            for (int i = 1; i < n; ++i) {
                new_classes[new_order[i]] = new_classes[new_order[i - 1]] + 
                    (make_pair(classes[new_order[i]], classes[safe(new_order[i] + l)]) != 
                        make_pair(classes[new_order[i - 1]], classes[safe(new_order[i - 1] + l)]));
            }
            swap(classes, new_classes);
            swap(order, new_order);
        }
        lcp.resize(n);
        id.resize(n);
        for (int i = 0; i < n; ++i)
            id[order[i]] = i;
        int tmp = 0;
        for (int i = 0; i < n; ++i) {
            if (id[i] == n - 1) {
                tmp = 0;
                continue; 
            }
            int j = order[id[i] + 1];
            while (s[i + tmp] == s[j + tmp])
                ++tmp;
            lcp[id[i]] = tmp;
            tmp = max(tmp - 1, 0);
        }
        for (int j = 0; j < K; ++j)
            table[j].resize(n);
        table[0] = lcp;
        for (int j = 1; j < K; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i)
                table[j][i] = min(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]);
        }
    }
    int get_lcp(int i, int j) {
        i = id[i];
        j = id[j];
        if (i == j)
            return -1;
        if (i > j)
            swap(i, j);
        int k = lg[j - i];
        return min(table[k][i], table[k][j - (1 << k)]);
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    /// reverse(s.begin(), s.end());
    string rs = s;
    reverse(rs.begin(), rs.end());
    string t = s + " " + rs;

    SuffMass arr(t);

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= k && i + j <= n; ++j) {
            int l3 = j;
            int l1 = 0;
            if (i > 0 && i + j < n) {
                l1 = arr.get_lcp(i + j, 2 * n + 1 - i);
            }
            ans = max(ans, 2 * l1 + l3 + k);
        }
    }

    auto is_pal = [&](int l, int r) {
        if (l < 0 || r > n) return false;
        if (l > r) return true;
        int len = arr.get_lcp(l, 2 * n + 1 - r);
        return len >= r - l;
    };

    for (int sum = 0; sum < 2 * n; ++sum) {
        int lft = -1, rgh = n;
        while (rgh - lft > 1) {
            int ml = (lft + rgh) / 2;
            int mr = sum - ml;
            if (is_pal(ml, mr)) {
                rgh = ml;
            } else {
                lft = ml;
            }
        }
        int ml = rgh, mr = sum - rgh;
        if (ml >= mr) continue;
        /// cerr << ml << " " << mr << endl;
        for (int j = 0; j <= k; ++j) {
            /// cerr << "j: " << j << endl;
            int pos1 = 2 * n + 1 - ml;
            int pos2 = mr + j;
            int l1 = 0;
            if (pos1 >= n + 1 && pos1 <= 2 * n && pos2 >= 0 && pos2 < n) {
                l1 = arr.get_lcp(pos1, pos2);
            }
            if (j + mr <= n) {
                ans = max(ans, 2 * l1 + 2 * j + mr - ml);
            }
            /// cerr << ans << endl;

            pos1 = 2 * n + 1 - ml + j;
            pos2 = mr;
            l1 = 0;
            if (pos1 >= n + 1 && pos1 <= 2 * n && pos2 >= 0 && pos2 < n) {
                l1 = arr.get_lcp(pos1, pos2);
            }
            if (j <= ml) {
                ans = max(ans, 2 * l1 + 2 * j + mr - ml);
            }
            /// cerr << ans << endl;
        }
        /// cerr << ans << "\n";
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    lg[0] = -1;
    for (int i = 1; i < MAXN; ++i)
        lg[i] = lg[i / 2] + 1;

    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    
    return 0;
}