[Solution] Expand the Path solution codeforces

Expand the Path solution codeforces – Consider a grid of size 𝑛×𝑛n×n. The rows are numbered top to bottom from 11 to 𝑛n, the columns are numbered left to right from 11 to 𝑛n.

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 𝑠s — the initial path of the robot. This path doesn’t lead the robot outside the grid.

Expand the Path solution codeforces

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.

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of testcases.

The first line of each testcase contains the single integer 𝑛n (2𝑛1082≤n≤108) — 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 21052⋅105.

Expand the Path solution codeforces

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.

Example

input

Copy
3
4
RD
5
DRDRDRDR
3
D

Expand the Path solution codeforces

13
9
3
Note

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

  • RD  RRD  RRRD  RRRDD  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  RRD  RRDD  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  RDD  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)

Expand the Path solution codeforces

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:

 

Expand the Path solution codeforces

Leave a Comment