题目背景

赛时提醒：当机器人在这棵完全二叉树的根时，执行 U 是非法的，即你需要保证不可能出现这种情况。

赛时提醒：这棵二叉树是无限向下延伸的，即所有节点均有左子节点与右子节点，除了根的所有节点均有父亲。

题目描述

小 X 捡到了一台复读机，这台复读机可以向机器人发号施令。机器人将站在一棵完全二叉树的根上，完全二叉树是无限延伸的。你将向复读机录入一串指令，这串指令单个字符可以是：

• L：命令机器人向当前节点的左子走；
• R：命令机器人向当前节点的右子走；
• U：命令机器人向当前节点的父亲走（若没有，则命令非法）。

录入指令后，复读机将会把指令无限复读下去。比如命令为 LR，那么机器人会遵从 LRLRLRLR... 一直走下去。

这棵完全二叉树上有一个 $n$ 个节点的连通块，保证这个连通块包含根节点。连通块上的每个节点都埋有宝藏，机器人到达过的地方如果有宝藏，则会将其开采。如果一个地方没有宝藏，机器人也可以到那里去。机器人也可以反复经过一个地方。

显然，这个连通块本身也是一棵二叉树。

现在，有人告诉了小 X 埋有宝藏的这棵二叉树的前序遍历，小 X 需要寻找到一条尽量短的指令，使得机器人能够挖掘出所有宝藏。

输入格式

一行一个字符串，由 0123 中的字符组成，表示埋有宝藏的这棵二叉树的前序遍历。

• 0：表示这是一个没有儿子的节点。
• 1：表示这是一个只有左子的节点。
• 2：表示这是一个只有右子的节点。
• 3：表示这是一个既有左子又有右子的节点。

输出格式

一个整数，表示最短指令的长度。

1313000

3

333003003300300

15

提示

【样例 1 说明】

一种可行的最短指令为 LRU。

本题采用捆绑测试。

• Subtask 1（31 points）：$2 \le n \le 10$。
• Subtask 2（32 points）：$2 \le n \le 200$。
• Subtask 3（37 points）：无特殊限制。

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^3$。