宝宝厌倦了整理房间，决定发明一个扫地机器人来帮他做家务。

我们将宝宝的房间视为一个拥有 $n$ 行 $m$ 列的网格，其中第 $i$ 行第 $j$ 列的格子记为 $(i, j)$。每个格子属于以下三种类型之一：

• 类型 0：该格子为空；
• 类型 1：该格子是墙；
• 类型 2：该格子有一件垃圾。

众所周知，房间四周都被墙包围。因此保证对于所有 $1 \le i \le n$，$(i, 1)$ 和 $(i, m)$ 都是墙；且对于所有 $1 \le j \le m$，$(1, j)$ 和 $(n, j)$ 都是墙。

经过几天的辛勤工作，宝宝成功制造出了他的第一个扫地机器人。该机器人配备了五个传感器、四个轮子、一个机械臂和一个非常简单的控制器。

传感器可以检测机器人当前所在格子的类型，以及相邻四个格子的类型。也就是说，如果机器人位于格子 $(i, j)$，它可以知道以下五个格子的类型：$(i, j)$、$(i - 1, j)$、$(i + 1, j)$、$(i, j - 1)$ 和 $(i, j + 1)$。

控制器接受一个长度恰好为 $243$（$243 = 3^5$）的字符串 $s$ 作为程序，其中每个字符代表一条指令，并根据程序和传感器返回的值来控制机器人。我们现在在下方列出所有有效的指令，并假设机器人当前位于格子 $(i, j)$：

• U：如果 $(i - 1, j)$ 不是墙，则将机器人从 $(i, j)$ 移动到 $(i - 1, j)$。否则什么都不做；
• D：如果 $(i + 1, j)$ 不是墙，则将机器人从 $(i, j)$ 移动到 $(i + 1, j)$。否则什么都不做；
• L：如果 $(i, j - 1)$ 不是墙，则将机器人从 $(i, j)$ 移动到 $(i, j - 1)$。否则什么都不做；
• R：如果 $(i, j + 1)$ 不是墙，则将机器人从 $(i, j)$ 移动到 $(i, j + 1)$。否则什么都不做；
• P：如果 $(i, j)$ 包含一件垃圾，机器人将捡起该垃圾。否则什么都不做。注意，捡起垃圾后，$(i, j)$ 变成空格子；
• I：什么都不做。

控制器的工作原理如下。注意，我们仍然假设机器人当前位于格子 $(i, j)$，并且我们用 $t(i, j)$ 表示格子 $(i, j)$ 的类型。

1. 计算 $x = 3^4 \times t(i, j) + 3^3 \times t(i - 1, j) + 3^2 \times t(i + 1, j) + 3 \times t(i, j - 1) + t(i, j + 1)$；
2. 读取 $s$ 中的第 $(x + 1)$ 个字符作为指令并执行。之后，返回步骤 1。

给定宝宝房间的地图、程序字符串以及机器人的起始位置，请计算机器人在执行 $k$ 条指令后可以捡起多少件垃圾。

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n, m$（$n, m \ge 3$，$n \times m \le 2000$），表示房间的大小。

第二行包含三个整数 $a, b$ 和 $k$（$1 < a < n$，$1 < b < m$，$1 \le k \le 10^{18}$），其中 $a$ 和 $b$ 表示机器人从格子 $(a, b)$ 开始出发，$k$ 表示机器人执行的指令数量。

第三行包含一个字符串 $s$（$|s| = 243 = 3^5$），表示输入控制器的程序。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $m$ 且仅由 '0'、'1' 和 '2' 组成的字符串 $r_i$（$|r_i| = m$），其中 $r_i$ 的第 $j$ 个字符表示格子 $(i, j)$ 的类型。

保证：

• 对于所有 $1 \le i \le n$，$(i, 1)$ 和 $(i, m)$ 都是墙；且对于所有 $1 \le j \le m$，$(1, j)$ 和 $(n, j)$ 都是墙；
• 格子 $(a, b)$ 不是墙；
• 所有测试数据的 $n \times m$ 之和不超过 $2 \times 10^4$。

输出格式

对于每组测试数据，输出一行包含一个整数，表示机器人在执行 $k$ 条指令后可以捡起的垃圾件数。

样例

输入 1

2
5 5
2 4 6
RUPIRPIUDDLRUDRURLIIURDLPRDLDIRLIDPPRRRLLULPRPUPPDPRIUIUDLULIRIDIRPUPPIRRLRLU >>
LUPLRIIRLPRLLRLDLLPDRUUDLDPRRPLLPPUIUUPPLUIILLDRIDILDRRUPLPPLPDLDPDDUPIPPUIIL >>
IPLUPLURRPIIDDPPIUPRPRIRDRPPIUIRDUUUPPPDIIRPURIUIUIPLRILLDPPPURPPRRPDPRRLUDUD >>
UDUPRLIUIRLR
11111
12021
10101
12021
11111
4 5
2 2 1000000000000000000
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII >>
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII >>
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII >>
IIIIIIIIIIII
11111
10021
11211
11111

输出 1

2
0

说明

在上述样例中，“>>” 表示当前行和下一行的内容在实际输入数据中其实是在同一行。由于它们太长，无法在一行中完整印出，因此我们在此处将其拆分为多行。更精确的输入示例请参见比赛网站。