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