Легенда гласить, що група монахів розв'язує задачу про Ханойські вежі. Задача про Ханойські вежі достатньо відома, складається з трьох стержнів та набору дисків різного розміру. Спочатку усі диски розміщені на одному стержні та упорядковані від найбільшого (знизу) до найменшого (зверху). Задача - перенести весь набір дисків на другой стержень, дотримуючись двох правил: 1) за один раз можна перекладувати лише один диск, і 2) не можна класти диск на стержень, зверху якого знаходиться менший диск. Монахи вірять, що коли вони закінчать роботу, то настане кінець світу. Припустимо, що Ви знаєте до якого стану у розв'язанні вони вже дійшли. Вважаючи що монахи перекладують диски оптимальним чином, скільки ще часу проіснує світ? \InputFile Вхідні дані складаються з декількох тестів. Кожен тест складається з одного рядка довжиною від \textbf{1} до \textbf{63} символів. Він містить лише (великі) \textbf{A}, \textbf{B} та \textbf{C}. Довжина рядка вказує на кількість дисків, а кожен з символів вказує на положення одного диска. Первший символ вказує на положення найменшого диску, другий символ - на положення другого найменшого диску, і так далі до останнього символу, який вказує на положення найбільшого диску. Символи \textbf{A}, \textbf{B} та \textbf{C} вказують на стержень, на якому знаходиться поточний диск. Вважайте, що завдання монахів - перекласти усі диски зі стержня \textbf{A} на стержень \textbf{B}, а у вхідних даних знаходиться допустимий поточний стан при оптимальному розв'язанні. Останні рядок містить велику \textbf{X} і не опрацьовується. \OutputFile Для кожного тесту вивести у окремому рядку одне число - кількість ходів, які ще потрібно здійснити для завершення розв'язання задачі про Ханойські вежі. Зайві пропуски не виводити, відповіді не відокремлювати порожніми рядками. Усі відповіді поміщаються у \textbf{64}-бітовое ціле число.