Trong bài toán Tháp Hà Nội, có ~N~ đĩa theo thứ tự từ nhỏ đến lớn đang nằm ở cột ~A~, quy tắc chuyển các đĩa như sau:

• Mỗi lần chỉ chuyển một đĩa.
• Đĩa nhỏ phải nằm trên đĩa lớn tại bất kỳ thời điểm nào trong quá trình chuyển.

Nhưng khác với bài tháp Hà Nội cổ điển, bài tháp Hà Nội Sắc Màu này, người ta sơn mỗi tầng tháp một màu và quy định luật chuyển cho mỗi loại tầng theo màu như mô tả trong bảng sau:

Ví dụ: với ~S =~ "xnxht" ta được một tháp như sau:

Bây giờ, Siro cần chuyển hết các đĩa từ cột ~A~ sang cột ~B~ theo quy tắc trên. Nhưng cậu không biết phải dùng ít nhất bao nhiêu lần chuyển để có thể chuyển hết số đĩa trên. Các bạn hãy giúp Siro nhé!

Input

Gồm ~1~ dòng duy nhất là ~1~ xâu ~S~ tượng trưng cho các đĩa trên cột ~A (1 \le |S| \le 15)~.

Output

Gồm ~1~ dòng chứa duy nhất ~1~ số nguyên dương là kết quả của bài toán trên.

Sample

Input #1

xnth

Output #1

28

Input #2

xn

Output #2

6

Input #3

xnxht

Output #3

31

Input #4

txnxh

Output #4

70

Hint

• Với #2 ta có các bước xếp đĩa sau:

~01~ ~A - B~

~02~ ~A - C~

~03~ ~B - C~

~04~ ~C - A~

~05~ ~C - B~

~06~ ~A - B~

Tổng cộng có ít nhất ~6~ lần xếp.