Problem Statement

There is an $H\times W$ grid of cells. Let $(h,w)$ denote the cell at the $h$-th row from the top and the $w$-th column from the left. Furthermore, you are given a string $S = S_1\cdots S_{H+W-2}$ of length $H+W-2$ consisting of D, R, and ?.

Initially, all cells are painted white. You may perform the following operation, which consists of three steps, any number of times:

1. Choose a string $X = X_1\cdots X_{H+W-2}$ of length $H+W-2$ satisfying all of the following.

• $X$ consists of exactly $H-1$ Ds and $W-1$ Rs.
  • For each $1 \le i \le H+W-2$, if $S_i$ is D then $X_i$ must also be D.
  • For each $1 \le i \le H+W-2$, if $S_i$ is R then $X_i$ must also be R.

2. Stand on cell $(1,1)$. Then for $i=1,2,\ldots$ in order, move one cell in the direction indicated by $X_i$: if $X_i$ is D, move down one cell; if $X_i$ is R, move right one cell. It can be shown that if $X$ satisfies the conditions in step 1, the destination cell always exists within the grid.
3. For every cell you visited in step 2 (including the starting and ending cells), if the cell is currently white, paint it black.

Find the maximum possible number of cells that can be painted black in total.

There are $T$ test cases; solve each one.

Constraints

• $1\le T\le 2\times 10^5$
• $2\le H,W\le 2\times 10^5$
• $T,H,W$ are integers.
• $S$ is a string of length $H+W-2$ consisting of D, R, and ?.
• The number of Ds in $S$ is at most $H-1$.
• The number of Rs in $S$ is at most $W-1$.
• The sum of $H+W$ over all test cases is at most $4\times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each case is given in the following format:

H W
S

Output

Print $T$ lines. The $i$-th line should contain the maximum number of cells that can be painted black for the $i$-th test case.