小Xはリピーター（復唱機）を拾いました。このリピーターはロボットに命令を送ることができます。ロボットは無限に広がる完全二分木の根に立っています。リピーターに命令の文字列を入力すると、その命令は無限に繰り返されます。命令の各文字は以下の通りです。

• L：ロボットに現在のノードの左の子へ移動するよう命令する。
• R：ロボットに現在のノードの右の子へ移動するよう命令する。
• U：ロボットに現在のノードの親へ移動するよう命令する（親が存在しない場合、この命令は無効）。

命令を入力すると、リピーターはその命令を無限に繰り返します。例えば命令が LR であれば、ロボットは LRLRLRLR... と動き続けます。

この完全二分木上には $n$ 個のノードからなる連結成分があり、この連結成分は根ノードを含んでいることが保証されています。連結成分上の各ノードには宝が埋まっており、ロボットが到達した場所に宝があれば採掘されます。宝がない場所であってもロボットは移動可能であり、同じ場所を何度も通過することも可能です。

明らかに、この連結成分自体も二分木です。

今、小Xは宝が埋まっているこの二分木の先行順巡回（前順走査）の結果を知らされました。小Xは、すべての宝を採掘できるような、できるだけ短い命令を見つける必要があります。

入力

1行の文字列が与えられる。この文字列は 0、1、2、3 から構成され、宝が埋まっている二分木の先行順巡回を表す。

• 0：子を持たないノードを表す。
• 1：左の子のみを持つノードを表す。
• 2：右の子のみを持つノードを表す。
• 3：左の子と右の子の両方を持つノードを表す。

出力

最短の命令の長さを表す整数を1つ出力せよ。

入出力例

入力 1

1313000

出力 1

3

注記 1

最短の命令の一例として LRU がある。

入力 2

333003003300300

出力 2

15

小課題

• Subtask 1（31点）：$2 \le n \le 10$。
• Subtask 2（32点）：$2 \le n \le 200$。
• Subtask 3（37点）：制約なし。

すべてのデータにおいて、$2 \le n \le 2 \times 10^3$ を満たす。