Mały X znalazł magnetofon, który potrafi wydawać polecenia robotowi. Robot zaczyna w korzeniu nieskończonego, pełnego drzewa binarnego. Wprowadzasz do magnetofonu ciąg instrukcji, w którym pojedyncze znaki mogą oznaczać:

• L: polecenie przejścia robota do lewego dziecka bieżącego węzła;
• R: polecenie przejścia robota do prawego dziecka bieżącego węzła;
• U: polecenie przejścia robota do rodzica bieżącego węzła (jeśli nie istnieje, polecenie jest nieprawidłowe).

Po wprowadzeniu instrukcji magnetofon będzie je powtarzał w nieskończoność. Na przykład, jeśli poleceniem jest LR, robot będzie wykonywał LRLRLRLR... i tak dalej.

W tym pełnym drzewie binarnym znajduje się spójny podzbiór $n$ węzłów, który zawiera korzeń drzewa. W każdym węźle tego podzbioru ukryty jest skarb. Jeśli robot dotrze do miejsca, w którym znajduje się skarb, zostanie on wydobyty. Robot może odwiedzać miejsca, w których nie ma skarbu, a także może wielokrotnie przechodzić przez ten sam węzeł.

Oczywiście ten spójny podzbiór sam w sobie również tworzy drzewo binarne.

Teraz ktoś przekazał małemu X-owi zapis przedrostkowy (preorder) tego drzewa binarnego ze skarbami. Mały X musi znaleźć jak najkrótszą instrukcję, dzięki której robot będzie w stanie wydobyć wszystkie skarby.

Wejście

Jeden wiersz zawierający ciąg znaków złożony z cyfr 0123, reprezentujący zapis przedrostkowy drzewa binarnego ze skarbami.

• 0: oznacza węzeł bez dzieci.
• 1: oznacza węzeł posiadający tylko lewe dziecko.
• 2: oznacza węzeł posiadający tylko prawe dziecko.
• 3: oznacza węzeł posiadający zarówno lewe, jak i prawe dziecko.

Wyjście

Jedna liczba całkowita oznaczająca długość najkrótszej instrukcji.

Przykład

Przykład 1

Wejście:

1313000

Wyjście:

3

Uwagi 1

Jedną z możliwych najkrótszych instrukcji jest LRU.

Przykład 2

Wejście:

333003003300300

Wyjście:

15

Podzadania

• Podzadanie 1 (31 punktów): $2 \le n \le 10$.
• Podzadanie 2 (32 punkty): $2 \le n \le 200$.
• Podzadanie 3 (37 punktów): brak dodatkowych ograniczeń.

Dla $100\%$ danych wejściowych: $2 \le n \le 2 \times 10^3$.