考虑点 $(x, y)$ 是否能被染色到。
若从 $(1, 1)$ 走到 $(x, y)$，我们设一共走了 $i = x + y - 2$ 步，可得出前 $i$ 步走了 $x-1$ 个 $\texttt{D}$ 和 $y-1$ 个 $\texttt{R}$。

设：$d_i, r_i, q_i$ 分别表示 $s$ 的前 $i$ 个字符中有多少个 $\texttt{D R ?}$。所以可得出以下不等式组：

$$\begin{cases} d_i \le x-1\\ r_i \le y -1\\ x-1-d_i \le \min(q_i, nd)\\ y-1-r_i \le \min(q_i, nr) \end{cases} $$

其中，$nd = n - 1 - d_{n + m - 2}, nr = m - 1 - r_{n + m - 2}$。 整理可得：

$$\begin{cases} d_i + 1 \le x \le \min(q_i, nd) + d_i + 1\\ r_i + 1 \le y \le \min(q_i, nr) + r_i + 1 \end{cases} $$

因为 $i = x + y - 2$，所以 $y = i - x + 2$。代入上不等式组，可将 $y$ 消掉：

$$\begin{cases} d_i + 1 \le x \le \min(q_i, nd) + d_i + 1\\ i - \min(q_i, nr) - r_i + 1 \le x \le i - r_i + 1 \end{cases} $$

合并可得：

$$\max(d_i + 1, i - \min(q_i, nr) - r_i + 1) \le x \le \min(\min(q_i, nd) + d_i + 1, i - r_i + 1) $$

则我们可以枚举 $i$ 来求出对于每一个 $i$，$x$ 的 个数。

还有一种方法是把所有靠前的问号先填 $\texttt{R}$，靠后的填 $\texttt{D}$，此时可以得到一条最靠上方的路径。再有一条所有靠前的问号填 $\texttt{D}$，靠后的问号填 $\texttt{R}$，可得到最靠下方的路径。这两条路径中间的格子一定可以被填。上下做差即可求和。

代码写的是第一种。

import sys

def solve():
    n, m = map(int, sys.stdin.readline().split())
    s = sys.stdin.readline().strip()
    total = n + m - 2
    
    d = [0] * (total + 1)
    r = [0] * (total + 1)
    q = [0] * (total + 1)

    # 计算前缀和
    for i in range(1, total + 1):
    d[i] = d[i-1] + (1 if s[i-1] == 'D' else 0)
    r[i] = r[i-1] + (1 if s[i-1] == 'R' else 0)
    q[i] = q[i-1] + (1 if s[i-1] == '?' else 0)
    
    # 计算缺失的D和R数量
    nd = n - 1 - d[total]
    nr = m - 1 - r[total]
    ans = 0

    # 核心计算逻辑
    for i in range(1, total + 1):
    term1 = min(min(q[i], nd) + d[i] + 1, i - r[i] + 1)
    term2 = max(d[i] + 1, i - min(q[i], nr) - r[i] + 1)
    ans += term1 - term2 + 1

    # 输出结果
    sys.stdout.write(f"{ans + 1}\n")

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
    solve()

if __name__ == "__main__":
    main()