#include<bits/stdc++.h>
using namespace std;

#define first_in_out ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long int
#define double long double
#define print(a) for(auto x : a) cout << x << " ";
#define printpair(a) for(auto x : a) cout << x.first << " " << x.second<<"\n";

int n, k;
string s;

int chk(int mid)
{
    int x = 0, a = 0;
    int res = 0;

    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'A') a++;
        else if (s[i] == 'B') res += a;
        else if (s[i] == '?') {
            if (mid <= 0) continue;
            x++;
            a++, mid--;
        }
    }

    int rem = k - x;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == 'A') a--;
        else if (s[i] == '?')
        {
            if (rem <= 0) continue;
            rem--;
            res += a;
        }
    }

    return res;
}

void solve()
{
    cin >> n >> k;
    cin >> s;

    int q = count(s.begin(), s.end(), '?');
    k = min(k, q);

    int left = 0, right = k, mid1, mid2, ans = chk(0);

    while (left <= right)
    {
        mid1 = left + (right - left) / 3;
        mid2 = right - (right - left) / 3;

        int aa = chk(mid1);
        int bb = chk(mid2);

        if (aa > bb)
        {
            ans = aa;
            left = mid1 + 1;
        }
        else if (bb > aa)
        {
            ans = bb;
            right = mid2 - 1;
        }
        else
        {
            left = mid1 + 1;
            right = mid2 - 1;
        }
    }

    for (int i = left; i <= right; i++)
        ans = max(ans, chk(i));

    cout << ans << "\n";
}

int32_t main()
{
    first_in_out
    int t = 1;
    cin >> t;

    while (t--)
        solve();
}