有一个 $n$ 行 $m$ 列的网格。每个格子要么是空的（用 . 表示），要么是被阻挡的（用 # 表示）。

你还得到了 $k$ 个拼图碎片，编号为 $1, 2, \dots, k$。每个碎片都是一个四连通的多格骨牌（polyomino），不能旋转或翻转。每个碎片由其最小外接矩形描述，其中 # 表示属于该碎片的格子，. 表示不属于该碎片的格子。

你需要选择这 $k$ 个碎片中的一部分，并将它们放置在网格上，使得：

• 每个被选择的碎片的每个格子必须恰好覆盖网格的一个空格子。
• 任意两个被选择的碎片不能覆盖同一个格子。
• 网格的每个空格子都必须恰好被一个被选择的碎片覆盖。

计算有效摆放方案的数量。当且仅当两种摆放方案使用了不同的拼图碎片集合，或者存在某个碎片在两种方案中覆盖的格子不同时，这两种方案被认为是不同的。

输入格式

输入包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。对于每个测试用例：

第一行包含三个整数 $n$，$m$ 和 $k$ ($1 \le n, m \le 8$，$1 \le k \le 8$)，表示网格的行数、列数和拼图碎片的数量。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述网格。这里 . 表示空格子，# 表示阻挡格子。保证网格中至少包含一个空格子。

然后描述 $k$ 个碎片。对于每个碎片，第一行包含两个整数 $r$ 和 $c$ ($1 \le r, c \le 8$)，表示其最小外接矩形的行数和列数。接下来的 $r$ 行，每行包含一个长度为 $c$ 的字符串，描述该碎片。保证每个碎片都是一个四连通的多格骨牌，且外接矩形的每一行和每一列都至少包含一个 #。

保证至多有 10 个测试用例满足 $k$ 大于 5。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示有效摆放方案的数量。

样例

输入格式 1

3
3 4 5
..#.
..#.
....
3 2
.#
.#
##
3 2
##
##
#.
3 2
.#
.#
##
1 3
###
2 1
#
#
2 2 2
..
..
1 1
#
1 2
##
2 2 3
..
..
1 1
#
1 1
#
1 2
##

输出格式 1

3
0
4

说明

第一组样例测试用例的 3 种摆放方案描述如下，其中整数表示碎片的编号。