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

#define int long long
#define endl "\n"
#define pii pair<int, int>
#define int long long


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

    int cnt = 0;
    for(auto ch : s) cnt += (ch == '?');

    k = min(k, cnt);

    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;
}

 
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();
	}
}