#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
    int a, b, gap_a, gap_b;
};
void solve()
{
    int n, k; cin >> n >> k;

    string s; cin >> s;
    vector<node> cnt(n);
    int a = 0, b = 0,gap = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'A')a++;
        if(s[i] == '?')gap++;
        cnt[i].a = a;
        cnt[i].gap_a = gap;
    }
    gap = 0;
    for(int i = n - 1; i >= 0 ; i--){
        cnt[i].b = b;
        cnt[i].gap_b = gap;
        if(s[i] == '?')gap++;
        if(s[i] == 'B')b++;
    }


    //a = 0, b = 0, gap = 0;
//    if(k >= gap){
//       ll mx = 0;
//        for(int i = 0; i < n; i++){
//            int tot_a = cnt[i].a + cnt[i].gap_a;
//            int tot_b = cnt[i].b + cnt[i].gap_b;
//            mx = max(mx, 1LL * tot_a * tot_b);
//        }
//
//        cout << mx << "\n";
//    }
//    else{
        k = min(k, gap);
        ll mx = 0;
        for(int i = 0; i < n; i++){
            int tmp_k = k;
            int tmp1 = cnt[i].a, tmp2 = cnt[i].b;
            if(tmp1 >= tmp2){
                int diff = tmp1 - tmp2;

                if(diff >= tmp_k){
                    tmp2 = tmp1;
                    tmp_k -= diff;
                    tmp1 += tmp_k / 2;
                    tmp2 += tmp_k - (tmp_k / 2);
                }
                else{
                    tmp2 += tmp_k;
                }
            }
            else{
                int diff = tmp2 - tmp1;

                if(diff >= tmp_k){
                    tmp1 = tmp2;
                    tmp_k -= diff;
                    tmp1 += tmp_k / 2;
                    tmp2 += tmp_k - (tmp_k / 2);
                }
                else{
                    tmp1 += tmp_k;
                }
            }
            mx = max(mx, 1LL * tmp1 * tmp2);
        }

        cout << mx << "\n";

//    }

}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	int t; cin >> t;

	while(t--){
        solve();
	}
}