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

/*#ifndef ONLINE_JUDGE
#include "DEBUG.h"
#define bug(...)           __f (#__VA_ARGS__, __VA_ARGS__)
#endif*/

#define first_in_out       ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll                 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;

ll chk(int mid)
{
	ll x = 0, a = 0;
	ll 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; ll ans = 0;

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

		ll aa = chk(mid1);
		ll 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";




}


int main()
{
	first_in_out

	int t = 1;
	cin >> t;

	while (t--)
		solve();

}