#include<bits/stdc++.h>
using namespace std;
//#define int long long
void solve()
{
    int n,k;cin>>n>>k;
    string s;cin>>s;
    int q=0,a=0,b=0;
    for(auto i:s)
    {
        if(i=='B')b++;
        else q++;
    }
    char d = 'p';
    vector<int>v;
    int ans=0;
    int preq=0;
    int gotb=0;
    for(auto i:s)
    {
        if(i=='A')
        {
            a++;
            ans+=b;
        }
        else if(i=='?')
        {
            preq++;
            if(a>b)
            {
                v.push_back(a);
                //ans+=a;
            }
            else
            {
                //ans+=b;
                v.push_back(b);
            }
        }
    }
    int rn = v.size();
    for(int i=0;i<min(k,rn);i++)
    {
        ans+=v[i];
        //cout<<i<<endl;
    }
    cout<<ans<<endl;
}
int32_t main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"Case : "<<i;
        solve();
    }

}