#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long countABSubsequences(string &s) {
    long long a_count = 0, ab_count = 0;
    for (char ch : s) {
        if (ch == 'A') {
            a_count++;
        } else if (ch == 'B') {
            ab_count += a_count;
        }
    }
    return ab_count;
}

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;

    vector<int> question_positions;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '?') question_positions.push_back(i);
    }

    for (int i : question_positions) {
        if (k <= 0) break;
        if (i > 0 && s[i - 1] == 'A') {
            s[i] = 'B';
            k--;
        } else if (i < n - 1 && s[i + 1] == 'B') {
            s[i] = 'A';
            k--;
        }
    }

    long long result = countABSubsequences(s);
    cout << result << endl;
}

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

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