#include <iostream>
using namespace std;

const int covertype[4][3][2] = {
    { {0,0}, {1,0}, {0,1} },
    { {0,0}, {0,1}, {1,1} },
    { {0,0}, {1,0}, {1,1} },
    { {0,0}, {1,0}, {1,-1} }};

bool cover(char** board,int y, int x, int ly, int lx,int &cnt, int h, int w);
bool findnext(char** board,int yc, int xc, int& yn, int& xn, int h, int w);

int main(int argc, char **argv)
{

    int C;
    cin >> C;


    while(C--)
    {
        char **board;
        int H,W;
        cin >> H >> W;

        board = (char**)malloc(sizeof(char*)*H);
        for(int i=0;i<H;i++)
        {
            board[i] = (char*)malloc(sizeof(char)*W+1);
        }
        cin.getline(board[0],W+1);
        for(int i=0;i<H;i++)
        {
            cin.getline(board[i],W+1);
        }

        bool firstblock =1;
        int fblock[2],lblock[2];

        int cnt=0;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(board[i][j]=='.'){
                    cnt++;
                    if(firstblock) {
                        fblock[0]=i;
                        fblock[1]=j;
                        firstblock=0;
                    }
                    lblock[0]=i;lblock[1]=j;
                }
            }
        }

        int numBlocks = cnt%3;
        int ret=0;
        if(numBlocks==0) 
        {
            cover(board,fblock[0],fblock[1],lblock[0],lblock[1],ret,H,W);
        }
        cout << ret << endl ;
        for(int i=0;i<H;i++){
            free(board[i]);
        }
        free(board);

    }
    return 0;
}

bool cover(char** board,int y, int x, int ly, int lx,int &cnt,int h, int w)
{
    if(y==ly)
        return false;

    for(int t=0;t<4;t++)
    {
        char** tmp=(char**)malloc(sizeof(char*)*h);
        for(int i=0;i<h;i++){
            tmp[i] = (char*)malloc(sizeof(char)*w+1);
            for(int j=0;j<w;j++)
            {
                tmp[i][j] = board[i][j];
                tmp[i][j+1]='\0';
            }
        }

        bool ok=true;
        bool last=false;
        for(int i=0;i<3;i++)
        {
            int dy=covertype[t][i][0];
            int dx=covertype[t][i][1];
            if(y+dy<h && x+dx<w)
            {
                if (tmp[y+dy][x+dx]!='.')
                    ok=false;
                else
                    tmp[y+dy][x+dx] = '@';


                if (y+dy==ly && x+dx==lx)
                    last=true;
            }
        }
        int yn, xn;
        bool flag =findnext(tmp,y,x,yn,xn,h,w);


        if(ok&&flag&&last)
            return false;
        else if(ok&&!flag&&last) {
            cnt++;
            return ok;
        }

        if(!ok&&t==3)
            return false;
        else if(ok&&flag){          
            cover(tmp,yn, xn, ly, lx, cnt,h,w);
        }

        for(int i=0;i<h;i++){
            free(tmp[i]);
        }
        free(tmp);


    }
}

bool findnext(char** board,int yc, int xc, int& yn,int& xn,int h, int w)
{
    for(int i=yc;i<h;i++){
        for(int j=xc;j<w;j++){
            if(board[i][j]=='.'){
                yn=i; xn=j;
                return true;
            }
        }
        xc=0;
    }
    return false;
}