//WA
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <ctime>

using namespace std;

typedef pair < int, int >     pii;
typedef long long int         i64;
typedef vector < pii >        vpii;
typedef pair < i64, i64 >     pi64;
typedef vector < int >        vi;
typedef vector < vi >         vvi;

#define rep(i,a,b)            for(int i=(int)a; i<(int)b; ++i)
#define rep_it(s,a,b)         for(s :: iterator it=a; it!= b; it++)
#define mp                    make_pair
#define pb                    push_back
#define clr(v)                v.clear()
#define mset(a,x)         memset(a, x, sizeof a)
#define all(v)                v.begin(), v.end()
#define err                   1E-8
#define inf                   (1<<29)
#define MAX                   1000

const int mR[4]={1,0,-1,0}, mC[4]={0,1,0,-1};

char M[45][21];
int f, mf, S, T, R, C, res[MAX][MAX];
bool taken[45][21];
vi p;

void augment(int u, int ed){
   if(u == S) f = ed;
   else if(p[u] != -1){
      augment(p[u], min(res[p[u]][u], ed));
      res[p[u]][u] -= f;
      res[u][p[u]] += f;
   }
}

int maxFlow(int N){
   mf = 0;
   int u;
   do{
      f = 0;

      p = vi(N, -1);
      vi dist(N, inf);
      queue < int > Q;
      Q.push(S);
      dist[S] = 0;

      while(!Q.empty()){
     u = Q.front(); Q.pop();
     if(u == T) break;
     rep(v,0,N) if(res[u][v] > 0 && dist[v]==inf)
        dist[v]=dist[u]+1, p[v]=u, Q.push(v);
      }
      augment(T, inf);
      mf += f;
   }while(f != 0);
}

#define can(_i,_j) (_i>=0 && _j>=0 && _i<R && _j<C)

int main(){
   int nT, cont;
   bool op;
   int ir, ic, u, v;
   vpii ast;
   map < pii, int > mapa;
   //char str[21];
   string str;
   //scanf("%d\n", &nT);
   cin >> nT;
   while(nT--){
      cont = 1;
      clr(ast); clr(mapa);
      mset(taken, false); mset(res, 0);

      //scanf("%d%d\n", &R, &C);
      cin >> R >> C;
      rep(i,0,R){
     //scanf("%s\n", str);
     cin >> str;
     rep(j,0,C) if(str[j] == '*') ast.pb(mp(i,j)), mapa[(mp(i,j))] = cont++;
     rep(j,0,C) M[i][j]=str[j];
      }
      S = 0;
      T = cont;

      rep(i,0,ast.size()){
     ir = ast[i].first;
     ic = ast[i].second;
     if(!taken[ir][ic]){
        queue < pii > Q;
        M[ir][ic] = (ir + ic) % 2 == 0 ? 'A' : 'B';
        Q.push(mp(ir, ic));
        while(!Q.empty()){
           ir = Q.front().first;
           ic = Q.front().second;
           Q.pop();

           if(taken[ir][ic]) continue;

           op = (M[ir][ic] == 'A');
           taken[ir][ic] = true;
           u = mapa[mp(ir, ic)];

           if(op) res[S][u] = 1;
           else res[u][T] = 1;

           rep(m,0,4) if(can(ir + mR[m], ic + mC[m]) && M[ir + mR[m]][ic + mC[m]] == '*'){
          M[ir + mR[m]][ic + mC[m]] = op ? 'B' : 'A';
          Q.push(mp(ir + mR[m], ic + mC[m]));

          v = mapa[mp(ir + mR[m], ic + mC[m])];
          if(op) res[u][v] = 1;
          else res[v][u] = 1;
           }
        }
     }
      }

      //rep(i,0,R){rep(j,0,C) cout << M[i][j]; cout << endl;}

      maxFlow(T+1);
      //printf("%d\n", cont - 1 - mf);
      cout << (cont - 1 - mf) << endl;
   }
   return 0;
}