E. Snake
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Calico Bear is convinced that no one can surpass his high score in Snake. Busy Beaver, thinking otherwise, would like to write an algorithm to prove him wrong.

Snake is played on an infinite 2D grid. A snake is a sequence of distinct cells forming a path from a head to a tail, where each consecutive pair of cells shares an edge. The length of the snake is the number of cells it contains.

The game begins at time $$$0$$$ with a single snake of length $$$1$$$, located at $$$(0, 0)$$$, and a single apple at some other location.

Busy Beaver will make a series of $$$N$$$ inputs in $$$\{\texttt{L}, \texttt{R}, \texttt{D}, \texttt{U}\}$$$ (left, right, down, up) to control the snake. Each input updates the snake as follows. First, the head moves one cell in the specified direction. Every other cell of the snake then shifts to the cell previously occupied by the preceding cell, leaving the tail unoccupied. If the head moves onto a cell containing an apple, the apple is eaten, and the snake grows a cell where the tail was before. A new apple then spawns on a cell not occupied by the snake.

An input is only valid if, after the update, no two cells of the snake coincide. It is guaranteed that no input opposes the previous one.

Let the score of the game be $$$\sum_{t=0}^N L_t$$$, where $$$L_t$$$ is the length of the snake at time $$$t$$$ (after $$$t$$$ inputs). Given the series of $$$N$$$ inputs, find the maximum possible score over all possible apple placements such that all inputs are valid.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$N$$$ ($$$1 \leq N \leq 5\cdot 10^3$$$).

The following line contains a string $$$s$$$ of $$$N$$$ characters ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{D}, \texttt{U}\}$$$), where $$$s_i$$$ represents the $$$i$$$-th input that Busy Beaver makes. No input opposes the previous one.

The sum of $$$N$$$ across all test cases does not exceed $$$5\cdot 10^3$$$.

Output

For each test case, output an integer answer on a new line.

Scoring

There are two subtasks for this problem.

  • ($$$60$$$ points): The sum of $$$N$$$ over all test cases does not exceed $$$500$$$.
  • ($$$40$$$ points): No additional constraints.
Example
Input
3
3
RRR
5
RDLUR
6
DDLURU
Output
10
18
22
Note

The example consists of three test cases.

In the first test case, the snake moves $$$3$$$ times. The snake is able to eat $$$3$$$ apples without colliding with itself. The score is $$$L_0+L_1+L_2+L_3=1+2+3+4=10$$$.

First test case, $$$t = 0, 1, 2, 3$$$ respectively

In the second test case, the snake moves $$$5$$$ times. The snake cannot get longer than $$$4$$$ since it only occupies $$$4$$$ cells. The score is $$$L_0+L_1+L_2+L_3+L_4+L_5=1+2+3+4+4+4=18$$$.

In the third test case, the snake moves $$$6$$$ times. The snake cannot get longer than $$$4$$$ since it has a loop of $$$4$$$ cells. After the loop, the snake cannot grow again because the apple should be spawned at time $$$3$$$, and at that time, the final cell is occupied by the tail of the snake. The score is $$$L_0+L_1+L_2+L_3+L_4+L_5+L_6=1+2+3+4+4+4+4=22$$$.

Third test case, first row shows $$$t = 0, 1, 2, 3$$$ and second row shows $$$t = 4, 5, 6$$$