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