#include<bits/stdc++.h>
const char nl = '\n';
#define SS " "
#define ddd cout<<"D"<<nl;
using namespace std;

void solve(){
	int n,k;cin>>n>>k;
	string s;cin>>s;
	int totB = 0, totA = 0, ptr1 = 0, ptr2 = n - 1, tmpAns = 0, ans = 0, cnt = 0, tmpA, tmpB, fnTmp = 0;
	for(int i = 0; i  < n; i++){
		if(s[i] == 'A')totA++;
		else if(s[i] == 'B')totB++;
	}
	tmpA = totA;
	tmpB = totB;
	for(int i = 0; i < n; i++){
		if(s[i] == 'B')tmpB--;
		else if(s[i] == 'A')fnTmp += tmpB;
	}
	// for(int i = n - 1; i >= 0; i--){
	// 	if(s[i] == 'A')tmpA--;
	// 	else if(s[i] == 'B')tmpAns += tmpA;
	// }
	// cout<<tmpAns<<nl;
	while(ptr1 < n && cnt < k){
		if(s[ptr1] == '?'){
			tmpAns += totB;
			totA++;
		}
		else if(s[ptr1] == 'B')totB--;
		cnt++;
		ptr1++;
	}
	ans = max(ans, tmpAns);
	// cout<<ans<<nl;
	while((ptr1 >= 0 || ptr2 >= 0) && cnt > 0){
		int f = 1;
		while(ptr2 >=0 && s[ptr2] != '?'){
			if(s[ptr1] == 'A')totA--;
			ptr2--;
		}
		// cout<<SS<<ptr2<<SS<<ptr1<<nl;
		if(ptr2 >= 0 && s[ptr2] == '?' && ptr2 > ptr1){
			tmpAns += totA;
			totB++;
			ptr2--;
			cnt--;
		}
		else if(ptr2 >= 0 && s[ptr2] == '?'){
			// ddd
			totA--;
			f = 0;
			tmpAns += totA;
			ptr2--;
			cnt--;
		}
		// cout<<SS<<tmpAns<<nl;
		while(ptr1 >=0 && s[ptr1] != '?'){
			if(s[ptr1] == 'B')totB++;
			ptr1--;
		}
		// cout<<ptr1<<SS<<totB<<nl;
		if(ptr1 >= 0 && s[ptr1] == '?'){
			tmpAns -= totB;
			if(f){
				totB++;
				totA--;
			}
			ptr1--;
		}
		
		ans = max(ans, tmpAns);
	}
	cout<<ans + fnTmp<<nl;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int T = 1;
	cin>>T;
	for(int  tc = 1; tc <= T; tc++){
		solve();
	}
}