#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;
    int a = 0, b = 0, q = 0;
    pair<int, int> found = {-1, -1};
    bool found_b  = false;
    int op = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'B' and found.first == -1){
            found = {1, i};
        }
        if(s[i] == 'B'){
            found_b = true;
        }
        if(found_b and s[i] == '?' and op < k){
            op++;
            s[i] = 'B';
        }
        if(s[i] == '?' and op < k) {s[i] = 'A'; op++;}
    }
    
    if(found.first == -1 and q == 0){
        cout << "0\n";
        return;
    }

    // cout << s << '\n';
    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';
}