← 返回题目列表

Codeforces · 1644/E

E. 扩展路径

中文机器翻译题面 查看原题

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

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

- D — 向下移动一个单元格;
- R — 向右移动一个单元格。

机器人不允许移动到网格之外。

您将获得一系列移动 $$$s$$$ — 机器人的初始路径。这条路径不会将机器人引导到网格之外。

您可以对其进行任意数量的修改(可能是零)。通过一项修改,您可以复制序列中的一个动作。即,将单个出现的 D 替换为 DD 或将单个出现的 R 替换为 RR。

计算单元格的数量,使得至少存在一个修改序列,机器人在修改的路径上访问该单元格并且不会移出网格。

输入

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

每个测试用例的第一行包含单个整数 $$$n$$$ ($$$2 \le n \le 10^8$$$) — 网格中的行数和列数。

每个测试用例的第二行包含一个非空字符串 $$$s$$$,仅由字符 D 和 R 组成,即机器人的初始路径。这条路径不会将机器人引导到网格之外。

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

输出

对于每个测试用例,打印一个整数 - 单元格的数量,使得至少存在一个修改序列,机器人在修改的路径上访问该单元格并且不会移出网格。

示例

输入 #1

3
4
RD
5
DRDRDRDR
3
D

输出 #1

13
9
3

注意

在第一个测试用例中,考虑以下修改路径就足够了:

- 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)$$$。

以下是所有测试用例的单元格: