A134860.午枫的教室路线

小午所在的教室被划分成一个 $H \times W$ 的方格，每个格子表示一个座位。

小午从左上角座位 $(1,1)$ 出发，需要走到右下角座位 $(H,W)$。

每一步只能向下（D）或向右（R）移动一格，总共需要走 $H+W-2$ 步。

现在给定一个长度为 $H+W-2$ 的字符串 $S$，其中：

• D 表示这一步必须向下走；
• R 表示这一步必须向右走；
• ? 表示这一步可以自由选择向下或向右。

对于每一种合法的走法，小午都会把路径上经过的所有座位（包括起点和终点）都标记为“已访问”。

现在，小午想知道：

在所有满足 $S$ 约束的路径中，最多可以让多少个不同的座位被访问到（至少一次）。

第一行输入一个整数 $T$，表示测试数据组数。

对于每组数据：

第一行输入两个整数 $H,W$，表示教室的行数和列数。

第二行输入一个长度为 $H+W-2$ 的字符串 $S$，由 D、R 和 ? 组成，表示移动规则。

对于每组数据，输出一行一个整数，表示最多可以被访问到的座位数量。

【解释说明】

样例 1 解释

小午可以选择不同的“?”路径，使得走出的路径覆盖尽可能多的座位。

例如可以通过不同的走法组合，让多个路径的访问区域尽可能“分散”，最终总共覆盖 $12$ 个不同座位。

【数据范围】

对于 $100\%$ 的测试数据，满足：

$1 \le T \le 2 \times 10^5$

$2 \le H,W \le 2 \times 10^5$

字符串 $S$ 长度为 $H+W-2$

保证至少存在一种合法路径

单个测试中 $\sum (H+W) \le 4 \times 10^5$