Alice is at the central point $(0,0)$ of an infinite Cartesian plane.

"'DURRRRR....' Bob shouts. "

Bob, being on Alice's tail, whispers in Alice's ears a string $s$ of length $n$. For each integer $1 \le i \le n$, the $i$-th instruction, $s_i$, is either U (up), D (down), L (left), or R (right), which means she should move one unit in the specified direction.

Rebelling against a controlling Bob, Alice only selectively listens to (and carries out) some instructions. As a programming enthusiast, she still carries out instructions in order. Formally, she selects a subsequence $t$ of $s$ and carries out each instruction in $t$, in order.

Note that a string $t$ is a subsequence of $s$ if and only if $t$ can be obtained from $s$ by removing several (possibly, zero or all) characters from $s$ and concatenating the remaining ones without changing their order. For example, DUR is a subsequence of DLUDR.

The point $(0,0)$ is a safe haven for Alice. Help Alice by telling her the maximum possible number of times she moves onto $(0,0)$.

Input

The first line of the input contains a positive integer $n$, denoting the number of instructions.

The second line of the input contains a string $s$ of $n$ instructions, denoting Bob's instruction whispered to Alice.

Output

Output a single non-negative integer, the maximum number of times Alice can move onto $(0,0)$, excluding the initial spawn.

Constraints

For all test cases, $1 \le n \le 2 \times 10^5$, the string $s$ contains characters U, D, L, and R only.

Subtask 1 (21 points): $n \le 18$.

Subtask 2 (23 points): $n \le 200$.

Subtask 3 (8 points): The string $s$ contains characters U and R only.

Subtask 4 (25 points): The string $s$ contains characters L and R only.

Subtask 5 (23 points): No additional constraints.