Маленький X нашел репитер, который может отдавать команды роботу. Робот начинает движение из корня бесконечного полного бинарного дерева. Вы вводите в репитер строку команд, где каждый символ может быть:

• L：приказывает роботу перейти к левому потомку текущего узла;
• R：приказывает роботу перейти к правому потомку текущего узла;
• U：приказывает роботу перейти к родителю текущего узла (если родителя нет, команда считается недопустимой).

После ввода команд репитер будет повторять их бесконечно. Например, если команда LR, робот будет двигаться по пути LRLRLRLR....

В этом полном бинарном дереве есть связная компонента из $n$ узлов, которая гарантированно содержит корень. В каждом узле этой компоненты спрятано сокровище. Если робот посещает узел, в котором есть сокровище, он его забирает. Робот может посещать узлы, в которых нет сокровищ, а также проходить через один и тот же узел несколько раз.

Очевидно, что эта компонента сама по себе также является бинарным деревом.

Теперь кто-то сообщил маленькому X прямое прохождение (префиксный обход) этого дерева с сокровищами. Маленькому X нужно найти кратчайшую последовательность команд, с помощью которой робот сможет собрать все сокровища.

Входные данные

Одна строка, состоящая из символов 0123, представляющая прямое прохождение дерева с сокровищами.

• 0：узел без потомков.
• 1：узел только с левым потомком.
• 2：узел только с правым потомком.
• 3：узел как с левым, так и с правым потомком.

Выходные данные

Одно целое число, представляющее длину кратчайшей последовательности команд.

Примеры

Пример 1

Входные данные

1313000

Выходные данные

3

Примечание

Одной из возможных кратчайших последовательностей команд является LRU.

Пример 2

Входные данные

333003003300300

Выходные данные

15

Подзадачи

• Подзадача 1 (31 балл): $2 \le n \le 10$.
• Подзадача 2 (32 балла): $2 \le n \le 200$.
• Подзадача 3 (37 баллов): без дополнительных ограничений.

Для $100\%$ данных $2 \le n \le 2 \times 10^3$.