#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
int t;
cin >> t;
while (t--){
ll n, k, mx = 0;
string s;
cin >> n >> k >> s;
s = '+' + s + '+';
vector<ll> a(n + 5), b(n + 5), cl(n + 5), cr(n + 5);
for (int i = 1; i <= n; i++){
a[i] = a[i - 1] + (s[i] == 'A');
cl[i] = cl[i - 1] + (s[i] == '?');
}
for (int i = n; i > 0; i--){
b[i] = b[i + 1] + (s[i] == 'B');
cr[i] = cr[i + 1] + (s[i] == '?');
}
for (int i = 1; i <= n; i++){
ll x = a[i];
ll y = b[i];
ll K = k;
ll l = cl[i - 1];
ll r = cr[i + 1];
if (x > y){
ll tmp = min({K, x - y, r});
y += tmp;
K -= tmp;
r -= tmp;
}
if (x < y){
ll tmp = min({K, y - x, l});
x += tmp;
K -= tmp;
l -= tmp;
}
int f = 1;
if (x > y){
if (K && s[i] == '?'){
y++, K--, f = 0;
}
}
if (y > x && f){
if (K && s[i] == '?'){
x++, K--, f = 0;
}
}
if (x == y && K && f && s[i] == '?'){
y++, K--;
}
ll tmp = min({K / 2, l + l, r + r});
x += tmp;
y += tmp;
l -= tmp, r -= tmp;
K -= (2 * tmp);
tmp = min(K, r);
if (K && r){
y += tmp;
K -= tmp;
}
tmp = min(K, l);
if (K && l){
x += tmp;
}
mx = max(mx, x * y);
}
cout << mx << endl;
}
return 0;
}