题目描述

给定一张 $n \times m$ 列的网格。在位于第 $i_h$ 行第 $j_h$ 列的格子上有一个洞。其它每个格子都是空地并且都有一只袋鼠。

相似地，袋鼠可以被键盘上的 U、D、L、R 键控制。所有袋鼠会同时根据按下的按键移动。具体来说，对于某个位于第 $i$ 行第 $j$ 列的袋鼠（用 $(i, j)$ 表示）上的袋鼠：

1. 按键 U：它会移动到 $(i - 1, j)$。
2. 按键 D：它会移动到 $(i + 1, j)$。
3. 按键 L：它会移动到 $(i, j - 1)$。
4. 按键 R：它会移动到 $(i, j + 1)$。

如果一只袋鼠跳到了洞（也就是说，$i = i_h$, $j = j_h$）或者移动到了网格外面，它将被从网格上移除。

问题在于，给你与 n、m 均未知的网格。您只知道一个由字符 U、D、L、R 组成的操作序列 $s$，以及一个整数 $k$ 表示应用这个操作序列之后，网格上恰有 $k$ 只袋鼠存留。

请计算有多少位置可能存在洞。也就是说，计算满足以下条件的整数对 $(i_h, j_h)$ 的数量：

• $1 \leq i_h \leq n$, $1 \leq j_h \leq m$。
• 洞位于 $(i_h, j_h)$。
• 应用给定的操作序列后，网格上恰有 $k$ 只袋鼠存留。

输入格式：

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

第一行输入三个整数 $n$, $m$, $k$ ($1 \leq n, m \leq 10^3$, $0 \leq k \leq n \times m$) 表示网格的大小以及应用操作序列后网格上存留的袋鼠数量。

接下来输入一个字符串 $s_{1, 2, \ldots, l}$ ($s_i \in \{U, D, L, R\}$, $1 \leq l \leq 10^6$) 表示操作序列。

所有输入数据 $n \times m$ 及以及操作序列长度之和均不超过 $10^6$。

输出格式：

对于每组测试数据，输出一个整数，表示洞可能存在的位置的数量。

样例

3 
4 5 3 
ULDDRR 
4 5 0 
UUUUUUU 
4 5 10 
UUUUUUU

2 
20 
0

解释#1

对于第一组测试数据：

第一个可能的洞的位置在 $(3,4)$

第二个可能的洞的位置在 $(4,3)$