#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 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 (right - left + 1 >= 3)
	{
		mid1 = left + (right - left) / 3;
		mid2 = right - (right - left) / 3;

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

		if (aa > bb)
			right = mid2 - 1;
		else
			left = mid1 + 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();

}