You are given a string path $S$ which consists of only four characters 'L', 'R', 'U', and 'D'. You are initially at origin $(0,0)$. You have to follow the directions as provided in path $S$ in order. For 'L' you have to move 1 unit left, for 'R' move 1 unit right, for 'U' move 1 unit up and for 'D' move 1 unit down.

You can do these operations any number of times:

• Delete any single move and remove it from the string path $S$.
• Convert any single move 'L' to 'R' or vice-versa.
• Convert any single move 'U' to 'D' or vice-versa.

Print the minimum operations required, after which going through the new path, you will meet the origin again.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• For each test case, you are given a string $S$ that denotes the path.

Output format

For each test case, print the minimum operations required in a new line.

Constraints

$1 \le T \le 100000\\ 1 \le |S| \le 200000$

It is guaranteed that the sum of the length of the string over $T$ test cases does not exceed 1000000.