小兔子被困在一个迷宫中，迷宫可以表示为一个 $n$ 行 $m$ 列的网格。迷宫中的一些方块是空地，另一些是墙壁。小兔子只能在空地上行走，不能进入墙壁或迷宫之外。

由于不知道该往哪里走，小兔子决定遵循一个固定的模式。该模式由一个长度为 $l$ 的字符串 $s$ 给出，其中仅包含 L、R、D 和 U。我们用 $(x, y)$ 表示第 $x$ 行第 $y$ 列的方块。L、R、D 和 U 的含义如下：

• L：从 $(x, y)$ 移动到 $(x, y - 1)$。
• R：从 $(x, y)$ 移动到 $(x, y + 1)$。
• D：从 $(x, y)$ 移动到 $(x + 1, y)$。
• U：从 $(x, y)$ 移动到 $(x - 1, y)$。

给定一个迷宫和一种模式 $s$，共有 $q$ 次询问。在每次询问中，给定 $x_1, y_1, z, x_2, y_2, a, b$。起初，小兔子位于 $(x_1, y_1)$。小兔子将从 $s_z$ 开始，并按 $s_z, s_{z+1}, \dots, s_l, s_1, s_2, \dots, s_l, s_1, s_2, \dots$ 的顺序循环且无限地遵循该模式。如果某次移动无效（例如移动到墙壁或迷宫之外），他将停留在当前位置，这也算作一步。你需要告诉小兔子在 $[a, b]$ 范围内有多少个整数 $u$，使得他在第 $u$ 步后位于 $(x_2, y_2)$。特殊地，认为他在第 $0$ 步后位于 $(x_1, y_1)$。

输入格式

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

每个测试用例的第一行包含三个整数 $n, m, q$ ($1 \le n, m \le 30, 1 \le q \le 3 \cdot 10^5$)，分别表示行数、列数和询问次数。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，仅包含 . 和 *。如果第 $x$ 个字符串的第 $y$ 个字符是 *，则方块 $(x, y)$ 是墙壁。否则，方块 $(x, y)$ 是空地。

接下来一行包含一个长度为 $l$ ($1 \le l \le 5000$) 的字符串，仅包含 L、R、D 和 U，表示固定的模式。

接下来 $q$ 行，每行包含七个整数 $x_1, y_1, z, x_2, y_2, a, b$ ($1 \le x_1, x_2 \le n, 1 \le y_1, y_2 \le m, 1 \le z \le l, 0 \le a \le b \le 10^9$)，表示一次询问。

输出格式

第 $x$ 个测试用例的输出以 Case #x: 开头，占一行。

接下来 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次询问的答案。

样例

样例输入 1

1
3 3 3
...
.*.
...
RRDDLLUU
1 1 1 3 3 1 1000
1 1 1 3 3 4 4
3 3 1 1 1 1 1000

样例输出 1

Case #1:
125
1
125