The Glitchy Robot#12466
A robot is placed at the origin on a 2D plane. It receives a sequence of moves as a string containing the characters:
'U' (Up): (x, y) \to (x, y + 1)
'D' (Down): (x, y) \to (x, y - 1)
'R' (Right): (x, y) \to (x + 1, y)
'L' (Left): (x, y) \to (x - 1, y)
Due to a system glitch, the robot can choose to skip exactly one move (ignore it completely) or execute the entire sequence normally. It cannot reorder the moves.
Your goal is to maximize the final Manhattan distance from the origin. The Manhattan distance between and is defined as |x| + |y|.
The first line contains an integer (1 \le T \le 10^4) — the number of test cases.
Each test case consists of a single string (1 \le |S| \le 2 \cdot 10^5) — the sequence of moves. The string contains only the characters U, D, L, and R.
It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.
For each test case, output a single integer: the maximum possible Manhattan distance from the origin after the sequence of moves (possibly skipping exactly one).
Example 1
Case 1 (UUD):
No skip: , Distance 2.
Skip D: Path is UU, ends at , Distance 2.
Skip U: Path is UD, ends at , Distance 0.
Max Distance = 2.
Case 2 (RRRL):
No skip: , Distance 2.
Skip L: Path RRR, ends at , Distance 3.
Max Distance = 3.
Case 3 (LDLD): No skip gives with distance 4.
Case 4 (UD): Skipping either move leaves the robot at distance 1.
Subtask ( points): 1 \le |S| \le 1000. The sum of over all test cases does not exceed .
Subtask ( points): No Additional Constraints.