Little X has found a repeater that can issue commands to a robot. The robot starts at the root of an infinitely extending complete binary tree. You will input a sequence of commands into the repeater, where each character in the sequence can be:
L: Commands the robot to move to the left child of the current node.R: Commands the robot to move to the right child of the current node.U: Commands the robot to move to the parent of the current node (if it does not exist, the command is invalid).
After the commands are entered, the repeater will repeat them infinitely. For example, if the command is LR, the robot will follow LRLRLRLR... and continue moving.
There is a connected component of $n$ nodes on this complete binary tree, and it is guaranteed that this component includes the root node. Each node in the connected component contains a treasure. If the robot reaches a location with a treasure, it will mine it. If a location has no treasure, the robot can still visit it. The robot can also pass through the same location multiple times.
Clearly, this connected component is itself a binary tree.
Now, someone has given Little X the preorder traversal of this binary tree containing the treasures. Little X needs to find the shortest possible command sequence such that the robot can mine all the treasures.
Input
A single string consisting of characters 0123, representing the preorder traversal of the binary tree containing the treasures.
0: Represents a node with no children.1: Represents a node with only a left child.2: Represents a node with only a right child.3: Represents a node with both a left and a right child.
Output
An integer representing the length of the shortest command sequence.
Examples
Input 1
1313000Output 1
3Note 1
One possible shortest command sequence is LRU.
Input 2
333003003300300Output 2
15Subtasks
- Subtask 1 (31 points): $2 \le n \le 10$.
- Subtask 2 (32 points): $2 \le n \le 200$.
- Subtask 3 (37 points): No special restrictions.
For $100\%$ of the data, $2 \le n \le 2 \times 10^3$.