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.