#include<bits/stdc++.h>
using namespace std; 
char nl = '\n';
using i64 = long long;

void solve(int t) {
    // cout << "test #" << t << nl;
    i64 n, k; cin >> n >> k;
    string str; cin >> str;
    vector<i64> cnt1(n + 1), cnt2(n + 1);
    i64 tot = 0, already = 0;
    i64 x = 0;
    i64 q = 0;
    for (auto& a : str) {
        tot += a == 'B';
    }
    for (int i = 0; i < n; i++) {
        if (str[i] == 'B') tot--;
        if (str[i] == '?') {
            q++;
            x++;
            already += tot;
            cnt1[x] = already;
        }
    }
    k = min(k, q);
    reverse(str.begin(), str.end());
    tot = 0; already = 0, x = 0;
    for (auto& a : str) {
        tot += a == 'A';
    }
    for (int i = 0; i < n; i++) {
        if (str[i] == 'A') tot--;
        if (str[i] == '?') {
            x++;
            already += tot;
            cnt2[x] = already;
        }
    }
    reverse(str.begin(), str.end());
    i64 ans = 0;
    for (i64 i = 0; i <= k; i++) {
        ans = max(ans, i * (k - i) + cnt1[i] + cnt2[k - i]);
        // cout << cnt1[i] << " " << cnt2[k - i] << nl;
    }
    tot = 0, already = 0, x = 0;
    for (int i = 0; i < n; i++) {
        tot += str[i] == 'B';
    }
    for (int i = 0; i < n; i++) {
        if (str[i] == 'A') {
            ans += tot;
        } else if (str[i] == 'B') {
            tot -= 1;
        }
    }
    cout << ans << nl;
} 

int main() {
    int tt = 1;
    cin >> tt;
    for(int t = 1; t <= tt; t++) solve(t);
}