CF1644E.Expand the Path

Consider a grid of size $n \times n$. The rows are numbered top to bottom from $1$ to $n$, the columns are numbered left to right from $1$ to $n$.

The robot is positioned in a cell $(1, 1)$. It can perform two types of moves:

• D — move one cell down;
• R — move one cell right.

The robot is not allowed to move outside the grid.

You are given a sequence of moves $s$ — the initial path of the robot. This path doesn't lead the robot outside the grid.

You are allowed to perform an arbitrary number of modifications to it (possibly, zero). With one modification, you can duplicate one move in the sequence. That is, replace a single occurrence of D with DD or a single occurrence of R with RR.

Count the number of cells such that there exists at least one sequence of modifications that the robot visits this cell on the modified path and doesn't move outside the grid.

考虑一个大小为 $n \times n$ 的网格。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。

机器人初始位于单元格 $(1, 1)$。它可执行两种类型的移动：

• D — 向下移动一格；
• R — 向右移动一格。

机器人不允许移出网格边界。

给定一个移动序列 $s$ —— 机器人的初始路径。该路径不会使机器人移出网格。

你可以对该序列执行任意次数（可能为零次）的修改。每次修改允许你复制序列中的某一次移动：即把某一个 D 替换为 DD，或把某一个 R 替换为 RR。

请计算满足以下条件的单元格个数：存在至少一种修改方式，使得机器人在修改后的路径中经过该单元格，且全程不移出网格。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains the single integer $n$ ($2 \le n \le 10^8$) — the number of rows and columns in the grid.

The second line of each testcase contains a non-empty string $s$, consisting only of characters D and R, — the initial path of the robot. This path doesn't lead the robot outside the grid.

The total length of strings $s$ over all testcases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^8$）—— 网格的行数与列数。

每个测试用例的第二行包含一个非空字符串 $s$，仅由字符 D 和 R 组成 —— 机器人的初始路径。该路径不会使机器人移出网格。

所有测试用例中字符串 $s$ 的总长度不超过 $2 \cdot 10^5$。

For each testcase, print a single integer — the number of cells such that there exists at least one sequence of modifications that the robot visits this cell on the modified path and doesn't move outside the grid.

对于每个测试用例，输出一个整数——满足以下条件的格子数量：存在至少一个修改序列，使得机器人在修改后的路径中访问该格子，且在整个过程中不移出网格边界。

In the first testcase, it's enough to consider the following modified paths:

• RD $\rightarrow$ RRD $\rightarrow$ RRRD $\rightarrow$ RRRDD $\rightarrow$ RRRDDD — this path visits cells $(1, 1)$, $(1, 2)$, $(1, 3)$, $(1, 4)$, $(2, 4)$, $(3, 4)$ and $(4, 4)$;
• RD $\rightarrow$ RRD $\rightarrow$ RRDD $\rightarrow$ RRDDD — this path visits cells $(1, 1)$, $(1, 2)$, $(1, 3)$, $(2, 3)$, $(3, 3)$ and $(4, 3)$;
• RD $\rightarrow$ RDD $\rightarrow$ RDDD — this path visits cells $(1, 1)$, $(1, 2)$, $(2, 2)$, $(3, 2)$ and $(4, 2)$.

Thus, the cells that are visited on at least one modified path are: $(1, 1)$, $(1, 2)$, $(1, 3)$, $(1, 4)$, $(2, 2)$, $(2, 3)$, $(2, 4)$, $(3, 2)$, $(3, 3)$, $(3, 4)$, $(4, 2)$, $(4, 3)$ and $(4, 4)$.

In the second testcase, there is no way to modify the sequence without moving the robot outside the grid. So the only visited cells are the ones that are visited on the path DRDRDRDR.

In the third testcase, the cells that are visited on at least one modified path are: $(1, 1)$, $(2, 1)$ and $(3, 1)$.

Here are the cells for all testcases:

在第一个测试用例中，只需考虑以下修改后的路径：

• RD $\rightarrow$ RRD $\rightarrow$ RRRD $\rightarrow$ RRRDD $\rightarrow$ RRRDDD —— 该路径访问的格子为 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 4)$、$(3, 4)$ 和 $(4, 4)$；
• RD $\rightarrow$ RRD $\rightarrow$ RRDD $\rightarrow$ RRDDD —— 该路径访问的格子为 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(2, 3)$、$(3, 3)$ 和 $(4, 3)$；
• RD $\rightarrow$ RDD $\rightarrow$ RDDD —— 该路径访问的格子为 $(1, 1)$、$(1, 2)$、$(2, 2)$、$(3, 2)$ 和 $(4, 2)$。

因此，在至少一条修改后的路径中被访问过的格子有：$(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 2)$、$(2, 3)$、$(2, 4)$、$(3, 2)$、$(3, 3)$、$(3, 4)$、$(4, 2)$、$(4, 3)$ 和 $(4, 4)$。

在第二个测试用例中，不存在任何不使机器人移出网格的序列修改方式。因此，唯一被访问的格子即为路径 DRDRDRDR 所经过的格子。

在第三个测试用例中，在至少一条修改后的路径中被访问过的格子有：$(1, 1)$、$(2, 1)$ 和 $(3, 1)$。

以下是所有测试用例中被访问的格子：