6_5

#include<iostream>
 
using namespace std;
int H, W;
char map[21][21];
 
int dx[4][2] = { { 1,1},{1,1},{1,0},{1,0} };
int dy[4][2] = { { 0,-1},{0,1},{1,1},{0,1} };
int ans;
int n_num;
int n;
bool isCovered[21][21];
void print()           
{
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cout << isCovered[i][j] << " ";
 
        }
        cout << endl;
 
    }
}
void cover()
{
    bool finished = true;
    int x = -1;
    int y = -1;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (map[i][j]=='.' && !isCovered[i][j])
            {
                x = i;
                y = j;
                finished = false;
                break;
            }
        }
 
        if (!finished)
        {
            break;
        }
    }
 
 
    if (finished)
    {
        ans += 1;
        return;
    }
 
 
    for (int d = 0; d < 4; d++)
    {
        int x0 = x + dx[d][0];
        int y0 = y + dy[d][0];
        int x1 = x + dx[d][1];
        int y1 = y + dy[d][1];
        if (map[x0][y0] == '.' && map[x1][y1] == '.' && x0 >= 0 && y0 >= 0 && x0 < H && y0 < W && x1 >= 0 && y1 >= 0 && x1 < H && y1 < W && !isCovered[x0][y0] && !isCovered[x1][y1])
        {
            isCovered[x][y] = true;
            isCovered[x0][y0] = true;
            isCovered[x1][y1] = true;
            //print();
            cover();
            isCovered[x][y] = false;
            isCovered[x0][y0] = false;
            isCovered[x1][y1] = false;
            //print();
        }
    }
 
    return;
}
  
int main()
{
    //freopen("input.txt", "r", stdin);
 
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        for (int i = 0; i < 21; i++)
        {
            for (int j = 0; j < 21; j++)
            {
                map[i][j] = '#';
                isCovered[i][j] = false;
            }
        }
 
        ans = 0;
        n_num = 0;
 
        cin >> H >> W;
 
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                cin >> map[i][j];
                if (map[i][j] == '#')
                {
                    isCovered[i][j] = true;
                }
                else if (map[i][j] = '.')
                {
                    n_num += 1;
                }
            }
        }
 
        if (n_num % 3 == 0)
        {
            cover();
        }
        else
        {
            ans = 0;
        }

        cout << ans << endl;
    }
    return 0;
}