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

#define int long long
#define endl "\n"
#define pii pair<int, int>
#define sz(x) (int) (x.size())


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

    priority_queue<int> pq;
    for(int i = 0; i < n; i++) {
        if(s[i] == '?') pq.push(i);
    }

    k = min(k, sz(pq));

    // int ans = 0, aCnt = 0;

    // for(int i = 0; i < n; i++) {
    //     if(s[i] == 'B') ans += aCnt;
    //     aCnt += (s[i] == 'A');
    // }

    // cerr<<"ans: "<<ans<<endl;

    // vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(k + 1, -1)));

    // function<int(int, int, int)> magic = [&] (int ind, int a, int op) {
    //     if(ind == n) return 0LL;
    //     int &ans = dp[ind][a][op];
    //     if(~ans) return ans;
    //     ans = 0;
    //     if(s[ind] == '?') {
    //         if(op + 1 <= k)
    //             ans = max(ans, magic(ind + 1, a + 1, op + 1));
    //         if(op + 1 <= k)
    //             ans = max(ans, a + magic(ind + 1, a, op + 1));
    //         ans = max(ans, magic(ind + 1, a, op));
    //     } else {
    //         ans = max(ans, (s[ind] == 'B' ? a : 0) + magic(ind + 1, a + (s[ind] == 'A'), op));
    //     }

    //     return ans;
    // };

    // cout<<magic(0, 0, 0)<<endl;

    int d = (k + 1) / 2;
    // ans += d * (k - d);

    // cerr<<"ans: "<<ans<<endl;

    for(int i = 1; i <= k && pq.size(); i++) {
        int ind = pq.top(); pq.pop();
        if(i <= d) {
            s[ind] = 'B';
        } else {
            s[ind] = 'A';
        }
    }

    // cerr<<"s: "<<s<<endl;

    int ans = 0, aCnt = 0;

    for(int i = 0; i < n; i++) {
        if(s[i] == 'B') ans += aCnt;
        aCnt += (s[i] == 'A');
    }

    // cerr<<"ans: "<<ans<<endl;

    cout<<ans<<endl;
}

 
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t = 1; cin>>t;
	for(int i = 1; i <= t; i++) {
		// cerr<<"Case "<<i<<": \n";
		solve();
	}
}