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