Problem Description

There is a robot that can move by receiving a sequence of commands.

There are four types of command in the command sequence:

• $U$: robot moves one unit up.


• $D$: robot moves one unit down.


• $L$: robot moves one unit left.


• $R$: robot moves one unit right.

Now, given a command sequence of length $n$. You need to find out how many substrings of the command sequence satisfy that if the robot execute the substring command, it can return to the starting position.

A substring is a contiguous sequence of characters within a string. For instance, "the best of" is a substring of "It was the best of times". For example, "Itwastimes" is a subsequence of "It was the best of times", but not a substring.

Input

This problem contains multiple test cases.

The first line contains an integer $t$ $(1 \leq t \leq 20)$ indicating the number of test cases.

For each test case, the first line contains one integer $n$ ($2 \leq n \leq 10 ^ 5$).

The second line contains a $UDLR$ string of length $n$.

Output

For each test case, output one line one integer indicating the answer.

1
6
URLLDR

2