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

typedef long long ll;
#define bug(x) cout<<#x<<" : "<<x<<endl;
#define bug2(a,b) cout<<#a<<" : "<<a<<"\t"<<#b<<" : "<<b<<endl;

int n;
string a,b;
const int N=1e5+7,M=200;
int dp[N][M];
vector<int>aa,bb;

int f(int i,char last){
	if(i==n){
		return 1;
	}
	if(dp[i][(last)]!=-1)return dp[i][(last)];
	int ans=0;
	if((last)<=(b[i]))ans=max(ans,f(i+1,(b[i]-'a')));
	if((last-'a')<=(a[i]-'a'))ans=max(ans,f(i+1,(a[i]-'a')));
	// bug(last)
	// bug(ans)
	return dp[i][(last-'a')]=ans;
}
signed main(){
	
	ll t=1;cin>>t;
	while(t--){
		int n,k;cin>>n>>k;
        string s;cin>>s;
        int a=0,b=0;
        ll ans=0;
        for(int i=0;i<n;i++){
            // bug(i)
            bool yes=0;
            if(s[i]=='?' and k>0){
                if(a==0){
                    s[i]='A';
                    k--;
                    // a++;
                    // continue;
                    goto niche;
                }
                if(a<b){
                    s[i]='A';
                    // a++;
                }
                else{
                    s[i]='B';
                    // b++;
                    // ans+=a;
                }
                k--;
                // continue;
            }
            // if(i==2){
            //     cout<<"Yup ";
            //     cout<<a<<' '<<b<<' '<<ans<<endl;;
            //     bug(yes)
            // }
            niche:
            if(s[i]=='B'){
                ans+=a;
                b++;
            }
            else if(s[i]=='A' )a++;
            // else if(s[i]=='B')b++;
            // cout<<i<<' '<<ans<<' '<<a<<' '<<b<<endl;
        }
        // cout<<s<<endl;
        cout<<ans<<endl;
	}
	return 0;
}