【题目背景】
协助少女找回了参加王选的徽章后，你得知那名少女名叫艾米莉亚，是一位王选候选人，住在一个叫罗兹瓦尔伯爵的宅子中。由于那枚徽章是王选的凭证，十分重要。为了感谢你，他们给了你一个许愿的机会，而为了留在艾米莉亚身边，你决定在这里当仆人。
【题目描述】
身为仆人的你，自然要帮忙打理宅子中的大花园。这个花园是一个NM的矩阵，修剪花草是一个比较复杂的任务。只能交给能干的女仆拉姆和雷姆，而你的任务只是要安排花园的布局。
在花园矩阵中的每个格子都要放入一个高度在1到NM的灌木，而罗兹瓦尔伯爵是一个很苛刻的人，他会指定一些格子，要求只有这些灌木的高度小于所有与它相邻灌木的高度（8相邻），并且他要求不能出现相同高度的灌木。为了圆满完成任务，你决定统计出共有多少种方案可以满足罗兹瓦尔的要求。
由于宅子十分大，搜易里面不只一个大花园，对于每个花园罗兹瓦尔伯爵都有独特的要求，你需要求出每个把所有花园的方案数。由于答案比较大，所以输出方案数模12345678后的结果。
【输入格式】
第一行，读入一个整数T表示T个花园。
对于每组数据，第一行，两个整数N,M表示花园矩阵的大小。
第二行到第N+1行，每行M个字符，如果当前字符是’.’表示这个格子不是罗兹瓦尔指定的格子，如果当前字符是’X’表示这个格子是罗兹瓦尔指定的格子。
【输出格子】
输出共T行，第i行表示第i个花园满足要求的方案数模12345678后的结果。
【输入样例】
2
3 2
X.
..
.X
2 2
X.
..
【输出样例】
60
6
【数据范围】
对于20%的数据：N*M<=10
另外有30%的数据，任意’.’字符都有一个相邻的’X’(8相邻)
对于100%的数据：N<=4,M<=7,T<=5