for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    if k * 2 > n:
        print(-1)
        continue
    ans = 0
    for i in range(k):
        ans += int(s[i] != 'R') + int(s[n - i - 1] != 'L')
    print(ans)

for _ in range(int(input())):
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    for i in range(n):
        a[i] -= c
    for i in range(n // 2):
        a[i] = max(a[i], 0)
    print(sum(a))

for _ in range(int(input())):
    n, k = map(int, input().split())
    if n == 1:
        if k == 1:
            print("YES")
            print(0)
        else:
            print("NO")
        continue
    k ^= n
    if k.bit_length() > (n - 1).bit_length():
        print("NO")
        continue
    s = list()
    if 0 < k <= n - 1:
        s.append(k)
    elif k:
        s.append(n - 1)
        s.append((n - 1) ^ k)
    s.append(0)
    a = s[:]
    for i in range(n):
        if i not in s:
            a.append(i)
    print("YES")
    print(*reversed(a))

#include <bits/stdc++.h>

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector b(n, std::vector<int>(n));
    while (m--) {
        int o, i, j;
        std::cin >> o >> i >> j;
        i--;
        j--;
        b[i][j] = b[j][i] = o;
    }
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        if (b[i][i] == 1 && b[j][j] == 2) {
            if (b[i][j] == 1) g[j].push_back(i);
            else g[i].push_back(j);
        }
    }
    std::vector<int> d(n), ans(n);
    for (int u = 0; u < n; u++) for (auto v : g[u]) d[v]++;
    int cnt = 0;
    std::queue<int> q;
    for (int u = 0; u < n; u++) if (!d[u]) q.push(u);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (b[u][u] == 1) ans[u] = ++cnt;
        else ans[u] = -(++cnt);
        for (auto v : g[u]) if (!--d[v]) q.push(v);
    }
    if (cnt == n) {
        for (int i = 0; i < n; i++) for (int j = i; j < n; j++) {
            if (b[i][j] == 1 && ans[i] + ans[j] < 0) return void(std::cout << "NO\n");
            if (b[i][j] == 2 && ans[i] + ans[j] >= 0) return void(std::cout << "NO\n");
        }
        std::cout << "YES\n";
        for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;
    while (t--) solve();
}

#include <bits/stdc++.h>

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector d(2, std::vector<int>(n));
    std::vector<std::vector<std::pair<int, int>>> g(n);
    while (m--) {
        int o, i, j;
        std::cin >> o >> i >> j;
        o--;
        i--;
        j--;
        g[i].emplace_back(j, o);
        g[j].emplace_back(i, o);
        d[o][i]++;
        d[o][j]++;
    }
    std::queue<int> q;
    std::vector<bool> vis(n);
    for (int i = 0; i < n; i++) if (d[0][i] == 0 || d[1][i] == 0) q.push(i), vis[i] = true;
    std::vector<std::pair<int, int>> t;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (d[0][u] == 0) t.emplace_back(u, -1);
        else t.emplace_back(u, 1);
        for (auto [v, o] : g[u]) if (!--d[o][v] && !vis[v]) {
            vis[v] = true;
            q.push(v);
        }
    }
    if (t.size() < n) return void(std::cout << "NO\n");
    std::cout << "YES\n";
    std::vector<int> ans(n);
    std::reverse(t.begin(), t.end());
    for (int i = 0; i < n; i++) ans[t[i].first] = (i + 1) * t[i].second;
    for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;
    while (t--) solve();
}

#include <bits/stdc++.h>

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    std::vector<bool> vis(n);
    long long ans = 0;
    int c = 0;
    auto dfs = [&](auto&& self, int u) -> void {
        vis[u] = true;
        for (auto v : g[u]) {
            if (g[v].size() & 1) ans += c++;
            else if (!vis[v]) self(self, v);
        }
    };
    for (int u = 0; u < n; u++) if (~g[u].size() & 1 && !vis[u]) {
        c = 0;
        dfs(dfs, u);
    }
    for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) ans += g[u].size() & g[v].size() & 1;
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;
    while (t--) solve();
}

M = 998244353
N = 501
fac = [0] * N
fac[0] = 1
for i in range(1, N):
    fac[i] = fac[i - 1] * i % M
inv = [0] * N
inv[-1] = pow(fac[-1], M - 2, M)
for i in range(N - 2, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % M
def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fac[n] * inv[k] % M * inv[n - k] % M

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if sum(max(0, v) for v in a) >= n:
        print(0)
        continue
    a.append(-1)
    f = [[[0] for _ in range(n)] for _ in range(n + 1)]
    g = [[0] * n for _ in range(n + 1)]
    for r in range(n):
        if a[r + 1] != -1:
            for l in range(n):
                f[l][r] = [0] * (a[r + 1] + 1)
    for i in range(1, n + 1):
        f[i][i - 1][0] = 1
        g[i][i - 1] = 1
    def w(i, k):
        if i == k:
            return 1 if a[k] <= 0 else 0
        else:
            return f[i][k - 1][a[k]] if a[k] != -1 else g[i][k - 1]
    for l in range(n - 1, -1, -1):
        for r in range(l, n):
            if a[r + 1] == -1:
                for k in range(l, r + 1):
                    g[l][r] = (g[l][r] + comb(r - l, k - l) * w(l, k) % M * g[k + 1][r] % M) % M
            else:
                for c in range(1, a[r + 1] + 1):
                    for k in range(l, r + 1):
                        f[l][r][c] = (f[l][r][c] + comb(r - l, k - l) * w(l, k) % M * f[k + 1][r][c - 1] % M) % M
    print(w(0, n))

#include <bits/stdc++.h>

std::string query(const std::vector<int>& a) {
    std::cout << "? " << a.size();
    for (auto v : a) std::cout << " " << v + 1;
    std::cout << std::endl;
    std::string s;
    std::cin >> s;
    return s;
}

std::vector<int> work(const std::vector<int>& a, const std::vector<int>& b) {
    if (a.empty() || b.empty()) return {};
    std::vector<int> s;
    for (auto v : a) s.push_back(v);
    for (auto v : b) s.push_back(v);
    std::string t = query(s);
    std::vector<int> r;
    for (int i = 0; i < b.size(); i++) if (t[i + a.size()] == '0') r.push_back(b[i]);
    return r;
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> g(n);
    auto find = [&](auto&& self, std::vector<int> a, std::vector<int> b) -> void {
        if (a.empty() || b.empty()) return;
        if (a.size() == 1) {
            for (auto v : b) g[v].push_back(a[0]), g[a[0]].push_back(v);
            return;
        }
        int m = a.size() / 2;
        std::vector a1(a.begin(), a.begin() + m), a2(a.begin() + m, a.end());
        auto p1 = work(a1, b);
        std::set<int> vis(p1.begin(), p1.end());
        std::vector<int> nb, p2;
        for (auto v : b) {
            if (vis.count(v)) nb.push_back(v);
            else p2.push_back(v);
        }
        self(self, a1, p1);
        for (auto v : work(a2, nb)) p2.push_back(v);
        self(self, a2, p2);
    };
    auto dfs = [&](auto&& self, std::vector<int> a) -> void {
        if (a.size() <= 1) return;
        std::string t = query(a);
        std::vector<int> p1, p2;
        for (int i = 0; i < a.size(); i++) {
            if (t[i] == '0') p2.push_back(a[i]);
            else p1.push_back(a[i]);
        }
        self(self, p2);
        std::vector<int> col(n, -1);
        std::vector<std::vector<int>> b(2);
        for (auto w : p2) if (col[w] == -1) {
            std::queue<int> q;
            q.push(w);
            col[w] = 0;
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                b[col[u]].push_back(u);
                for (auto v : g[u]) if (col[v] == -1) {
                    col[v] = col[u] ^ 1;
                    q.push(v);
                }
            }
        }
        for (int i = 0; i < 2; i++) {
            find(find, b[i], work(b[i], p1));
        }
    };
    std::vector<int> a(n);
    std::iota(a.begin(), a.end(), 0);
    dfs(dfs, a);
    std::cout << "!" << std::endl;
    for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) std::cout << u + 1 << " " << v + 1 << std::endl;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;
    while (t--) solve();
}

Tutorial will be added after the first official solve.