#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long int ll;
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define mod 1000000007
ll lcm(ll a,ll b)
{
return (a*b)/__gcd(a,b);
}
ll binExp(ll a,ll b)
{
if(b==0)
return 1;
ll res=binExp(a,b/2);
if(b&1)
{
return (a*res*res)%mod;
}
else
{
return (res*res)%mod;
}
}
bool isPrime(long long n)
{
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (long long i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
class DisjointSet
{
public:
vector<ll> parent,rnk,sz;
DisjointSet(ll n)
{
rnk.resize(n+1,0);
parent.resize(n+1);
sz.resize(n+1);
for(ll i=0; i<=n; i++)
{
parent[i]=i;
sz[i]=1;
}
}
ll findUPar(ll node)
{
if(node==parent[node])
{
return node;
}
return parent[node]=findUPar(parent[node]);
}
bool unionByRank(ll u,ll v)
{
ll ulp_u=findUPar(u);
ll ulp_v=findUPar(v);
if(ulp_u==ulp_v)
{
return false;
}
if(rnk[ulp_u]==rnk[ulp_v])
{
parent[ulp_u]=ulp_v;
rnk[ulp_v]++;
}
else if(rnk[ulp_u]<rnk[ulp_v])
{
parent[ulp_u]=ulp_v;
}
else if(rnk[ulp_v]<rnk[ulp_u])
{
parent[ulp_v]=ulp_u;
}
return true;
}
bool unionBYSize(ll u,ll v)
{
ll ulp_u=findUPar(u);
ll ulp_v=findUPar(v);
if(ulp_u==ulp_v)
return false;
if(sz[ulp_u]<sz[ulp_v])
{
parent[ulp_u]=ulp_v;
sz[ulp_v]+=sz[ulp_u];
}
else
{
parent[ulp_v]=ulp_u;
sz[ulp_v]+=sz[ulp_u];
}
return true;
}
};
void solve()
{
ll n,k;
cin>>n>>k;
string str;
cin>>str;
ll numA[n];
ll numB[n];
ll sumA=0;
ll sumB=0;
ll cnt=0;
for(ll i=0; i<n; i++)
{
if(str[i]=='A')
{
sumA++;
}
else if(str[i]=='B')
{
sumB++;
}
else if(str[i]=='?')
{
cnt++;
}
numA[i]=sumA;
numB[i]=sumB;
}
ll xx=min(cnt,k);
ll i=0;
while(i<n && xx>0)
{
if(str[i]=='?')
{
xx--;
ll temp1=numB[n-1]-numB[i];
ll temp2=0;
if(i-1>=0)
temp2=numA[i-1];
if(temp1>temp2)
{
str[i]='A';
}
else if(temp2>=temp1)
{
str[i]='B';
}
}
i++;
}
ll cntB[n];
ll sum=0;
for(ll i=n-1; i>=0; i--)
{
if(str[i]=='B')
{
sum++;
}
cntB[i]=sum;
}
ll ans=0;
for(ll i=0; i<n; i++)
{
if(str[i]=='A')
{
ans+=(cntB[i]);
}
}
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin>>t;
//t=1;
ll caseNo=1;
while(t--)
{
//cout<<"Case "<<caseNo<<": ";
// caseNo++;
solve();
}
return 0;
}