boardcover

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int h, w;
int typeselect1[3][2] = { {0,0},{1,0},{1,1} };//x,y순
int typeselect2[3][2] = { {0,0},{1,0},{0,1} };
int typeselect3[3][2] = { {0,0},{0,1},{1,1} };
int typeselect4[3][2] = { {0,0},{0,1},{-1,1} };

int canItCover(char arr[20][20], int x, int y, int type) {
if (type == 1) {
int ax,ay,bx,by,cx,cy;
ax = x + typeselect1[0][0];
if (ax < 0 || ax >= w)return false;
ay = y + typeselect1[0][1];
if (ay < 0 || ay >= h)return false;
bx = x + typeselect1[1][0];
if (ax < 0 || ax >= w)return false;
by = y + typeselect1[1][1];
if (ay < 0 || ay >= h)return false;
cx = x + typeselect1[2][0];
if (ax < 0 || ax >= w)return false;
cy = y + typeselect1[2][1];
if (ay < 0 || ay >= h)return false;
if (arr[ay][ax] != '.')return false;
if (arr[by][bx] != '.')return false;
if (arr[cy][cx] != '.')return false;
return true;

}
else if (type == 2) {
int ax, ay, bx, by, cx, cy;
ax = x + typeselect2[0][0];
if (ax < 0 || ax >= w)return false;
ay = y + typeselect2[0][1];
if (ay < 0 || ay >= h)return false;
bx = x + typeselect2[1][0];
if (ax < 0 || ax >= w)return false;
by = y + typeselect2[1][1];
if (ay < 0 || ay >= h)return false;
cx = x + typeselect2[2][0];
if (ax < 0 || ax >= w)return false;
cy = y + typeselect2[2][1];
if (ay < 0 || ay >= h)return false;
if (arr[ay][ax] != '.')return false;
if (arr[by][bx] != '.')return false;
if (arr[cy][cx] != '.')return false;
return true;
}
else if (type == 3) {
int ax, ay, bx, by, cx, cy;
ax = x + typeselect3[0][0];
if (ax < 0 || ax >= w)return false;
ay = y + typeselect3[0][1];
if (ay < 0 || ay >= h)return false;
bx = x + typeselect3[1][0];
if (ax < 0 || ax >= w)return false;
by = y + typeselect3[1][1];
if (ay < 0 || ay >= h)return false;
cx = x + typeselect3[2][0];
if (ax < 0 || ax >= w)return false;
cy = y + typeselect3[2][1];
if (ay < 0 || ay >= h)return false;
if (arr[ay][ax] != '.')return false;
if (arr[by][bx] != '.')return false;
if (arr[cy][cx] != '.')return false;
return true;
}
else if (type == 4) {
int ax, ay, bx, by, cx, cy;
ax = x + typeselect4[0][0];
if (ax < 0 || ax >= w)return false;
ay = y + typeselect4[0][1];
if (ay < 0 || ay >= h)return false;
bx = x + typeselect4[1][0];
if (ax < 0 || ax >= w)return false;
by = y + typeselect4[1][1];
if (ay < 0 || ay >= h)return false;
cx = x + typeselect4[2][0];
if (ax < 0 || ax >= w)return false;
cy = y + typeselect4[2][1];
if (ay < 0 || ay >= h)return false;
if (arr[ay][ax] != '.')return false;
if (arr[by][bx] != '.')return false;
if (arr[cy][cx] != '.')return false;
return true;
}
}


int cover(char arr[20][20]) {
int ret = 0;
int count = 0;
int test = 0;
int findi=-1, findj=-1;

for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (arr[i][j] == '.') { count++; }
}
}
if (count % 3 != 0)return 0;
if (count == 0)return 1;


for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
test = 0;
if (arr[i][j] == '.') {
findi = i; findj = j;
break;
}
}
if (findi != -1)break;
}
if (canItCover(arr, findj, findi, 1)) {
arr[findi][findj] = '#';
arr[findi + typeselect1[1][1]][findj + typeselect1[1][0]] = '#';
arr[findi + typeselect1[2][1]][findj + typeselect1[2][0]] = '#';
ret = ret + cover(arr);
arr[findi][findj] = '.';
arr[findi + typeselect1[1][1]][findj + typeselect1[1][0]] = '.';
arr[findi + typeselect1[2][1]][findj + typeselect1[2][0]] = '.';
}
if (canItCover(arr, findj, findi, 2)) {
arr[findi][findj] = '#';
arr[findi + typeselect2[1][1]][findj + typeselect2[1][0]] = '#';
arr[findi + typeselect2[2][1]][findj + typeselect2[2][0]] = '#';
ret = ret + cover(arr);
arr[findi][findj] = '.';
arr[findi + typeselect2[1][1]][findj + typeselect2[1][0]] = '.';
arr[findi + typeselect2[2][1]][findj + typeselect2[2][0]] = '.';
}
if (canItCover(arr, findj, findi, 3)) {
arr[findi][findj] = '#';
arr[findi + typeselect3[1][1]][findj + typeselect3[1][0]] = '#';
arr[findi + typeselect3[2][1]][findj + typeselect3[2][0]] = '#';
ret = ret + cover(arr);
arr[findi][findj] = '.';
arr[findi + typeselect3[1][1]][findj + typeselect3[1][0]] = '.';
arr[findi + typeselect3[2][1]][findj + typeselect3[2][0]] = '.';
}
if (canItCover(arr, findj, findi, 4)) {
arr[findi][findj] = '#';
arr[findi + typeselect4[1][1]][findj + typeselect4[1][0]] = '#';
arr[findi + typeselect4[2][1]][findj + typeselect4[2][0]] = '#';
ret = ret + cover(arr);
arr[findi][findj] = '.';
arr[findi + typeselect4[1][1]][findj + typeselect4[1][0]] = '.';
arr[findi + typeselect4[2][1]][findj + typeselect4[2][0]] = '.';
}
return ret;
}




int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);

int c;
cin >> c;
for (int i = 0; i < c; i++) {
cin >> h >> w;
char arr[20][20];
for (int j = 0; j < h; j++) {
for (int k = 0; k < w; k++) {
char a;
cin >> a;
arr[j][k] = a;
}
}
int key;
key = cover(arr);
cout << key<<"\n";



}

}