#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define all(v) v.begin(),v.end()
#define nl "\n"
#define FIO \
    ios_base::sync_with_stdio(false);\
    cin.tie(NULL);\
    cout.tie(NULL);

void solve()
{
    ll n,k; cin >> n >> k;

    string s; cin >> s;

    ll cnt = 0;
    for(ll i = 0; i < n; i++)   if(s[i] == '?')cnt++;
    if(k > cnt) k = cnt;

  
    ll b=count(all(s), 'B'), a=0;
    for(ll i=0; i<n; i++){
        
        if(s[i]=='A') a++;
        else if(s[i]=='B') b--;
        else if(k!=0){
            if((a+1)*b>=a*(b+1)) s[i]='A', a++;
            else s[i]='B', b++;
            k--;
        }
        if(k==0)    break;
    }
    // cout<<s<<nl;
    a=0;
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        if(s[i]=='A')   a++;
        else if(s[i]=='B')  ans+=a;
    }
    cout<<ans<<nl;

}

int32_t main()
{
    ll t=1;
    cin>>t;
    for(ll i=1;i<=t;i++)
    {
        // cout<<"Case "<<i<<": ";
        solve();
    }
}