#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;
        }
      }
      
      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;
      }
      if (x == y && K && f && s[i] == '?'){
        y++, K--;
      }
      mx = max(mx, x * y);
    }
    cout << mx << endl;
  }
  return 0;
}