CF1391B.Fix You

Consider a conveyor belt represented using a grid consisting of $n$ rows and $m$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is labelled $(i,j)$.

Every cell, except $(n,m)$, has a direction R (Right) or D (Down) assigned to it. If the cell $(i,j)$ is assigned direction R, any luggage kept on that will move to the cell $(i,j+1)$. Similarly, if the cell $(i,j)$ is assigned direction D, any luggage kept on that will move to the cell $(i+1,j)$. If at any moment, the luggage moves out of the grid, it is considered to be lost.

There is a counter at the cell $(n,m)$ from where all luggage is picked. A conveyor belt is called functional if and only if any luggage reaches the counter regardless of which cell it is placed in initially. More formally, for every cell $(i,j)$, any luggage placed in this cell should eventually end up in the cell $(n,m)$.

This may not hold initially; you are, however, allowed to change the directions of some cells to make the conveyor belt functional. Please determine the minimum amount of cells you have to change.

Please note that it is always possible to make any conveyor belt functional by changing the directions of some set of cells.

考虑一条由 $n$ 行 $m$ 列组成的网格表示的传送带。从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子记为 $(i,j)$。

除终点格子 $(n,m)$ 外，每个格子均被赋予一个方向：R（右）或 D（下）。若格子 $(i,j)$ 被赋予方向 R，则放置于该格子上的行李将移动至格子 $(i,j+1)$；类似地，若格子 $(i,j)$ 被赋予方向 D，则行李将移动至格子 $(i+1,j)$。若在任意时刻行李移出网格边界，则视为丢失。

在格子 $(n,m)$ 处设有一个计数器，所有行李最终均从此处被取走。当且仅当无论初始放置于哪个格子，行李最终均能抵达该计数器时，称该传送带是功能完备的（functional）。更形式化地说：对每个格子 $(i,j)$，初始置于该格子的行李最终必须到达格子 $(n,m)$。

这一性质在初始状态下未必成立；但你可以修改若干格子的方向，以使传送带变为功能完备的。请确定所需修改的最少格子数量。

请注意：总可以通过修改某组格子的方向，使得任意传送带变为功能完备的。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). Description of the test cases follows.

The first line of each test case contains two integers $n, m$ ($1 \le n \le 100$, $1 \le m \le 100$) — the number of rows and columns, respectively.

The following $n$ lines each contain $m$ characters. The $j$-th character in the $i$-th line, $a_{i,j}$ is the initial direction of the cell $(i, j)$. Please note that $a_{n,m}=$ C.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$（$1 \le n \le 100$，$1 \le m \le 100$），分别表示行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个字符。第 $i$ 行中的第 $j$ 个字符 $a_{i,j}$ 表示单元格 $(i, j)$ 的初始方向。请注意：$a_{n,m}=$ C。

For each case, output in a new line the minimum number of cells that you have to change to make the conveyor belt functional.

对于每组测试数据，在一行中输出使传送带正常工作所需修改的最少格子数。

In the first case, just changing the direction of $(2,3)$ to D is enough.

You can verify that the resulting belt is functional. For example, if we place any luggage at $(2,2)$, it first moves to $(3,2)$ and then to $(3,3)$.

In the second case, we have no option but to change the first $3$ cells from D to R making the grid equal to RRRC.

在第一种情况下，只需将 $(2,3)$ 处的方向改为 D 即可。

你可以验证，所得传送带是功能正常的。例如，若在 $(2,2)$ 处放置任意行李，它将首先移动到 $(3,2)$，然后移动到 $(3,3)$。

在第二种情况下，我们别无选择，只能将前 $3$ 个格子的方向由 D 改为 R，从而使网格变为 RRRC。