有一天，Little Q 醒来时发现自己身处一个二维像素世界。这个世界是一个 $n \times m$ 的网格。Little Q 只能沿着这些单元格的边行走，这意味着他只能停留在坐标 $(x, y)$ 处，当且仅当 $0 \le x \le n$ 且 $0 \le y \le m$，其中 $x$ 和 $y$ 为整数。每个单元格的中心都写有一个数字，数字 $w_{i,j}$ ($1 \le i \le n, 1 \le j \le m$) 写在点 $(i - 0.5, j - 0.5)$ 处。

Little Q 不知道如何逃离这个像素世界，于是他开始漫游。你将收到 $q$ 次询问，每次询问包含两个整数 $(x, y)$ 和一个字符串 $S$，表示 Little Q 的路线。最初，Little Q 站在 $(x, y)$，然后他将依次执行 $|S|$ 步移动 $S_1, S_2, \dots, S_{|S|}$。以下是每种移动方式的具体含义：

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

保证 Little Q 永远不会走出像素世界，且路线将构成一个简单多边形。对于每次询问，请告诉 Little Q 该路线所形成的多边形内部有多少个不同的数字。

幸运的是，在解决这个问题后，Little Q 在床上醒来了。原来像素世界只是一场梦！

输入格式

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

第一行包含三个整数 $n, m, q$ ($1 \le n, m \le 400, 1 \le q \le 200\,000$)，分别表示像素世界的维度和询问次数。

接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行包含 $m$ 个整数 $w_{i,1}, w_{i,2}, \dots, w_{i,m}$ ($1 \le w_{i,j} \le n \times m$)，表示每个单元格中写的数字。（注意：如果你希望“U”确实表示“向上”，你可能需要旋转此表示法等。）

接下来的 $q$ 行，每行包含两个整数 $x$ 和 $y$ ($0 \le x \le n, 0 \le y \le m$) 以及一个非空字符串 $S$ ($S_i \in \{L, R, D, U\}$)，描述每次询问。

保证 $\sum |S| \le 4\,000\,000$。

输出格式

对于每次询问，输出一行，包含一个整数：多边形内部有多少个不同的数字。

样例

输入 1

1
3 3 2
1 2 3
1 1 2
7 8 9
0 0 RRRUUULLLDDD
0 0 RRUULLDD

输出 1

6
2