#include <bits/stdc++.h>
#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define nl '\n'
// vector<int> primes;
// bool is_prime[(int)1e7 + 10];
using namespace std;
void solve();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout<<"Case "<<i<<": ";
        solve();
    }
}
// seive here
//  void seive(int n)
//  {
//      is_prime[0] = is_prime[1] = 1;
//      for (int i = 4; i <= 1e7 + 10; i += 2)
//      {
//          is_prime[i] = 1;
//      }
//      for (int i = 3; i * i <= 1e7 + 10; i += 2)
//      {
//          if (is_prime[i] == 0)
//          {
//              for (int j = i + i; j <= 1e7 + 10; j += i)
//              {
//                  is_prime[j] = 1;
//              }
//          }
//      }

//     //for finding primes in a single vector
//     // for (int i = 0; i <= 1e7 + 10; i++)
//     // {
//     //     if (is_prime[i] == 0)
//     //     {
//     //         primes.push_back(i);
//     //     }
//     // }

//     //return;
// }

void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    string res;
    bool afound = false, bfound = false;
    int op = 0;
    for (int i = 0; i < n; i++)
    {
        if(s[i]=='A')afound=true;
        if(s[i]=='B')bfound=true;
        if (afound and op < k and s[i] == '?')
        {
            s[i] = 'B';
            op++;
        }
        if ((!afound) and op < k and s[i] == '?')
        {
            s[i] = 'A';
            afound = 1;
            op++;
        }
    }

    if (!afound and k == 0)
    {
        cout << 0 << endl;
        return;
    }

    //cout<<s<<endl;
    vector<int> pos;
    int BB = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == 'A')
        {
            pos.push_back(BB);
        }
        else if (s[i] == 'B')
            BB++;
    }
    cout << accumulate(all(pos), 0) << '\n';
}