题目描述

设计师明理正在给一块矩形棋盘铺设装饰砖。棋盘有 $n$ 行 $m$ 列，每个格子中是字符 * 或 .。

一种三格骨牌由一个棋盘格作为中心，再加上两个与中心有公共边的相邻格组成。如果这两个非中心格还拥有一个公共顶点，那么称这种三格骨牌为 L 形三格骨牌。

你可以在棋盘上画出若干个互不重叠的 L 形三格骨牌。要求：

• 每个 L 形三格骨牌的中心格必须是 *；
• 棋盘上每个 * 都必须恰好作为某个三格骨牌的中心；
• 所有三格骨牌的非中心格都必须是 .。

请计算满足条件的绘制方案数。答案可能很大，只需输出它对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

对于每个测试用例：

第一行包含两个整数 $n,m$，表示棋盘的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个字符，每个字符为 * 或 .，表示棋盘。

输出格式

对于每个测试用例，输出一行一个整数，表示满足条件的绘制方案数。

数据范围

• $1\le t\le 250000$；
• $2\le n,m\le 100$；
• 所有测试用例的 $n\cdot m$ 之和不超过 $1000000$。

样例 1

输入

3
3 3
...
.*.
...
3 3
*..
...
..*
3 3
...
..*
.*.

输出

4
1
0