#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        vector<ll> a(n), b(n);
        if (s[0] == '?')
        {
            if (k <= 0)
            {
                continue;
            }
            s[0] = 'A';
            k--;
        }
        if (s[n - 1] == '?')
        {
            if (k <= 0)
            {
                continue;
            }
            s[n - 1] = 'B';
            k--;
        }

        for (int i = 0; i <= n / 2; i++)
        {
            if (k <= 0)
            {
                break;
            }
            if (s[i] == '?')
            {
                k--;
                s[i] = 'A';
            }
        }

        for (int i = n / 2; i < n; i++)
        {
            if (k <= 0)
            {
                break;
            }
            if (s[i] == '?')
            {
                k--;
                s[i] = 'B';
            }
        }
        ll cta = 0, ctb = 0;
        bool ok1 = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (!ok1 and s[i] == 'B')
            {
                ok1 = 1;
            }
            if (ok1 and s[i] == 'A')
            {
                cta++;
            }
        }
        bool ok2 = 0;
        for (int i = 0; i < n; i++)
        {
            if (!ok2 and s[i] == 'A')
            {
                ok2 = 1;
            }
            if (ok2 and s[i] == 'B')
            {
                ctb++;
            }
        }

        //  ll cta=count(s.begin(),s.end(),'A');
        //         ll ctb=count(s.begin(),s.end(),'B');
        cout << cta * ctb << endl;
    }
}