/*
    40*10的地圖，有一些'*'必須用方塊覆蓋到
    而每塊方塊只能覆蓋長度為1*2
    問最少需要的方塊數(shù)

    狀態(tài)壓縮dp，主要就是枚舉當(dāng)前行的狀態(tài)to，上一行的狀態(tài)from,由from的值去更新to的值

    骨牌覆蓋類求方案數(shù)的，一般都需要枚舉所有情況，即放、不放
    但這種求最優(yōu)值的，我一開始枚舉所有情況，導(dǎo)致超時!!
    需要人肉優(yōu)化
    比如，這里空的位置肯定不用放東西，直接下一列

    這道題，轉(zhuǎn)移時只需考慮當(dāng)前row和上一行row-1，
    對于列col 分4種情況，
    00 01 10 11
    1表示該位置是'*'
    分這4種情況：
    ①不放 狀態(tài)構(gòu)造為 to<<1 , from<<1
    ②上一行有'*'  狀態(tài)構(gòu)造為 to<<1 , from<<1|1
    ③當(dāng)前行有'*'  由于上一行沒有，就沒必要豎放了，直接橫放了，豎放不會導(dǎo)致最優(yōu)解
       然后還要考察col+1是否有'*'，有的話狀態(tài)要加上去
       當(dāng)然，該位置可以不放，為了給下一行覆蓋
    ④上下行都有'*'
       不放的話，上一行就需要有覆蓋了
       橫放，上一行肯定就要被覆蓋了
       豎放，上一行可選擇被覆蓋，或者沒被覆蓋
       但選擇被覆蓋是不會導(dǎo)致最優(yōu)解的，因為橫放的時候就會考慮上一行該位置要被覆蓋了
        

    求最優(yōu)值（不是求方案），沒必要轉(zhuǎn)移時 from -> to 把一些明顯不優(yōu)的狀態(tài)from轉(zhuǎn)移到to去
    如對于'O'位置，可以放，但肯定不去放它，放了不會更優(yōu)的，所以不進入這個分支了
    分支數(shù)決定了規(guī)模，人肉優(yōu)化，不進入沒必要的分支
    但求方案數(shù)目的話，就要考慮所有情況了，放、不放之類的
*/    
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>

using namespace std;

const int INF = 1000000000;

char field[50][20];
int dp[50][1<<10];
int H, W;

void dfs(int row, int col , int s1 , int s2 , int num){//當(dāng)前檢查col
    /*if(col > W){
        return;
    }*/
    if(col >=  W){//因為可能在最后一列水平覆蓋，所以出格了
        if(col>W){//注意>>
            s1 >>= 1;
            s2 >>= 1;
        }
        dp[row][s1] = min(dp[row][s1] , dp[row-1][s2] + num);
        return;
    }
    int code = (field[row][col] == '*')*2 + (field[row-1][col] == '*');
    
    switch(code){
        case 0:
            dfs(row, col+1, s1<<1, s2<<1, num);            
            break;
        case 1:
            dfs(row, col+1, s1<<1, s2<<1|1, num);//用|去覆蓋(row-1,col)跟(row-1,col)自己覆蓋效果一樣
            break;
        case 2:
            dfs(row, col+2, (s1<<2)|2|(field[row][col+1] == '*'), (s2<<2)|(field[row-1][col+1] == '*'), num+1);
            //nothing
            dfs(row, col+1, s1<<1, s2<<1, num);
            break;
        case 3:
            //nothing
            dfs(row, col+1, s1<<1, s2<<1|1, num);
            dfs(row, col+1, s1<<1|1, s2<<1, num+1);
            //dfs(row, col+1, s1<<1|1, s2<<1|1, num+1);  s2<<1|1在下面的狀態(tài)會考慮到的，而且下面的不會比它差 所以不用再dfs
            dfs(row, col+2, (s1<<2)|2|(field[row][col+1] == '*'), (s2<<2)|2|(field[row-1][col+1] == '*'), num+1);
            break;
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
#endif

    int T;
    for(scanf("%d",&T); T-- ;){
        scanf("%d%d",&H,&W);
        for(int i = 1 ; i <= H; i++){
            scanf("%s",field[i]);
        }    
        for(int row = 1 ; row <= H ; row++){
            fill(dp[row] , dp[row] + (1<<W), INF);
            dfs(row,0,0,0,0);
        }
        int ans = INF;
        int mask = 0;
        for(int i = 0; i < W ; i++){
            mask <<= 1;
            mask |= (field[H][i] == '*');
        }
        for(; mask < (1<<W);mask++){
            ans = min(ans, dp[H][mask]);
        }
        printf("%d\n",ans);
    }    
    return 0;
}