Легенда гласит, что группа монахов решает задачу о Ханойских башнях. Задача про Ханойские башни достаточно известная, состоит из трех стержней и набора дисков разного размера. Изначально все диски расположены на одном стержне и упорядочены от наибольшего (внизу) до наименьшего (сверху). Задача - перенести весь набор дисков на другой стержень, следуя двум правилам: 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}-битовое целое число.