二维网格图（也称为方格网图）是一个具有 $nm$ 个顶点的无向图，对应于 $n \times m$ 网格中的所有节点。此处的边是对网格中连接两个相邻节点的长度为一的火柴棍的抽象描述。

现在，Rikka 给定你一个由不超过 $(2nm - n - m)$ 条边组成的 $n \times m$ 网格图。她希望你计算该无向图的不同定向方式的数量，使得定向后的图是一个没有有向环的有向图。

在本题中，无向图的定向是指为每条边指定一个方向，从而将初始图转化为有向图。

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 60$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 6$)，分别表示网格图的列数和行数。

接下来有 $(2n - 1)$ 行，每行最多包含 $(2m - 1)$ 个字符，用于描述网格图。奇数行包含网格顶点（用分隔的加号 ‘+’ 表示）以及零个或多个水平边，而偶数行包含零个或多个垂直边。具体而言，输入中表示了所有可能的顶点。每个连接相邻顶点的水平边用单个减号 ‘-’ 表示，每个垂直边用单个竖线 ‘|’ 表示。边字符将精确放置在对应顶点之间。所有其他字符均为空格。

注意，如果任何输入行包含尾随空格，这些空格将被忽略。

输出格式

对于每个测试用例，输出一行，包含一个整数，即给定网格图的有效定向数量。

样例

输入 1

4
2 2
+-+
+ +
2 2
+-+
|
+ +
2 2
+-+
|
+-+
2 2
+-+
| |
+-+

输出 1

2
4
8
14