Background

Contest Reminder: Executing U is illegal when the robot is at the root of this complete binary tree, meaning you need to ensure this situation cannot occur.

Contest Reminder: This binary tree extends infinitely downward, meaning all nodes have both a left and a right child, except for the root which has no parent.

Problem Description

Xiao X has found a repeater, which can command a robot. The robot will stand at the root of a complete binary tree that extends infinitely. You will input a sequence of commands into the repeater, where each command is a single character:

• 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 exists, otherwise the command is illegal).

After inputting the commands, the repeater will repeat the commands infinitely. For example, if the command is LR, the robot will follow LRLRLRLR... indefinitely.

There is a connected block of $n$ nodes in this complete binary tree, guaranteed to include the root node. Each node in this connected block contains treasure, and the robot will mine any treasure at places it visits. The robot can also visit places without treasure and can repeatedly pass through the same place.

Clearly, this connected block itself is also a binary tree.

Now, someone has told Xiao X the preorder traversal of the binary tree containing the treasure, and Xiao X needs to find a shortest sequence of commands that allows the robot to mine all the treasure.

Input Format

A single line of string consisting of characters from 0123, representing the preorder traversal of the binary tree containing the treasure.

• 0: Indicates a node with no children.
• 1: Indicates a node with only a left child.
• 2: Indicates a node with only a right child.
• 3: Indicates a node with both left and right children.

Output Format

An integer representing the length of the shortest sequence of commands.

Sample Input and Output

Sample Input #1

1313000

Sample Output #1

3

Sample Input #2

333003003300300

Sample Output #2

15

Notes

This problem uses batched tests.

• 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$.

见题面 Input 部分

见题面 Output 部分