#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    int t; cin>>t;
    while (t--)
    {   
       ll n, k; cin >> n >> k;
       string s; cin >> s;
       vector<ll> a(n), b(n);
       if(s[0]=='?'){
        s[0]='A';
       }
       if(s[n-1]=='?'){
        s[n-1]='B';
       }

      


        for(int i=0; i<n/2; i++)
        { if(s[i]=='?'){
        s[i]='A';
       }
           
        }
        
        for(int i=n/2; i<n; i++)
        { if(s[i]=='?'){
        s[i]='B';
       }
      
           
        }

 ll cta=count(s.begin(),s.end(),'A');
        ll ctb=count(s.begin(),s.end(),'B');
        cout<<cta*ctb<<endl;




    }
    
}