#P1644E. Expand the Path

    ID: 103 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forcecombinatoricsdata structuresimplementationmath*1900

Expand the Path

Description

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

The robot is positioned in a cell (1,1)(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 ss — 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.

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

The first line of each testcase contains the single integer nn (2n1082 \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 ss, 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 ss over all testcases doesn't exceed 21052 \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.

Input

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

The first line of each testcase contains the single integer nn (2n1082 \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 ss, 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 ss over all testcases doesn't exceed 21052 \cdot 10^5.

Output

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.

Samples

样例输入 1

3
4
RD
5
DRDRDRDR
3
D

样例输出 1

13
9
3

Note

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, 1), (1,2)(1, 2), (1,3)(1, 3), (1,4)(1, 4), (2,4)(2, 4), (3,4)(3, 4) and (4,4)(4, 4);
  • RD \rightarrow RRD \rightarrow RRDD \rightarrow RRDDD — this path visits cells (1,1)(1, 1), (1,2)(1, 2), (1,3)(1, 3), (2,3)(2, 3), (3,3)(3, 3) and (4,3)(4, 3);
  • RD \rightarrow RDD \rightarrow RDDD — this path visits cells (1,1)(1, 1), (1,2)(1, 2), (2,2)(2, 2), (3,2)(3, 2) and (4,2)(4, 2).

Thus, the cells that are visited on at least one modified path are: (1,1)(1, 1), (1,2)(1, 2), (1,3)(1, 3), (1,4)(1, 4), (2,2)(2, 2), (2,3)(2, 3), (2,4)(2, 4), (3,2)(3, 2), (3,3)(3, 3), (3,4)(3, 4), (4,2)(4, 2), (4,3)(4, 3) and (4,4)(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)(1, 1), (2,1)(2, 1) and (3,1)(3, 1).

Here are the cells for all testcases: