#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5,inf=1e9;
struct node
{
    int v,nxt,w;
}e[maxn];
int head[maxn],tot=1;
void add(int x,int y,int w)
{
    e[++tot]=(node){y,head[x],w};
    head[x]=tot;
    e[++tot]=(node){x,head[y],0};
    head[y]=tot;
}
int de[maxn],s,t,n,m,vis[maxn],now[maxn];
int bfs()
{
    int S=s,T=t;
    memset(de,0x3f,sizeof de);
    queue<int> q;
    q.push(S);
    de[S]=0;
    now[S]=head[S];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            int v=e[i].v,w=e[i].w; 
            // cout<<"###"<<x<<' '<<v<<' '<<w<<'\n';
            if(w&&de[v]>de[x]+1)
            {
                de[v]=de[x]+1;
                now[v]=head[v];
                if(v==T)
                    return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
int dfs(int x,int flow)
{
    if(x==t)
        return flow;
    int res=0;
    for(int i=now[x];i;i=e[i].nxt)
    {
        int v=e[i].v,w=e[i].w;
        now[x]=i;
        // cout<<"###"<<x<<' '<<v<<' '<<w<<'\n';
        if(!w||de[v]!=de[x]+1||flow==res)
            continue;
        int tl=dfs(v,min(w,flow-res));
        e[i].w-=tl,e[i^1].w+=tl;
        res+=tl;
    }
    if(!res)
        de[x]=INT_MAX;
    return res;
}
int cnt,id[105][105];
char a[105][105];
int main()
{
    // freopen("matrix.in","r",stdin);
    // freopen("matrix.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0); 
    int _;
    cin>>_;
    while(_--)
    {
        memset(head,0,sizeof head);
        tot=1;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                if(a[i][j]=='B')
                    a[i][j]='1';
                if(a[i][j]=='W')
                    a[i][j]='0';
                if((i+j)&1)
                {
                    if(a[i][j]=='1')
                        a[i][j]='0';
                    else if(a[i][j]=='0')
                        a[i][j]='1';
                }

            }
        s=++cnt,t=++cnt;
        
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=1;j<=m;j++)
        //         cout<<a[i][j];
        //     cout<<'\n';
        // }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                id[i][j]=++cnt;
        int qwq=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(a[i][j]!='0')
                    add(s,id[i][j],1);
                if(a[i][j]!='1')
                    add(id[i][j],t,1);
                if(a[i][j]=='?')
                    ++qwq;
            }
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=1;j<=m;j++)
        //         cout<<a[i][j];
        //     cout
        // }
        int ans=0;
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
            {
                ++ans,++ans;
                ++cnt;
                add(s,cnt,1);
                add(cnt,id[i][j],inf);
                add(cnt,id[i+1][j],inf);
                add(cnt,id[i][j+1],inf);
                add(cnt,id[i+1][j+1],inf);
                ++cnt;
                add(cnt,t,1);
                add(id[i][j],cnt,inf);
                add(id[i+1][j],cnt,inf);
                add(id[i][j+1],cnt,inf);
                add(id[i+1][j+1],cnt,inf);
            }
        // cout<<ans<<'\n';
        while(bfs())
            ans-=dfs(s,inf);
        cout<<ans+qwq<<'\n';
    } 
    return 0;
}