The End of the World

Legend says that there is a group of monks who are solving a large Towers of Hanoi puzzle. The Towers of Hanoi is a well-known puzzle, consisting of three pegs, with a stack of disks, each a different size. At the start, all of the disks are stacked on one of the pegs, and ordered from largest (on the bottom) to smallest (on the top). The object is to move this stack of disks to another peg, subject to two rules: 1) you can only move one disk at a time, and 2) you cannot move a disk onto a peg if that peg already has a smaller disk on it.

The monks believe that when they finish, the world will end. Suppose you know how far they’ve gotten. Assuming that the monks are pursuing the most efficient solution, how much time does the world have

There will be up to $2\,
048$ test cases in the input. Each test case will
consist of a string of length $1$ to $63$, on a single line. This string
will contain only (capital) **A**s,
**B**s and **C**s. The
length of the string indicates the number of disks, and each
character indicates the position of one disk. The first
character tells the position of the smallest disk, the second
character tells the position of the second smallest disk, and
so on, until the last character, which tells the position of
the largest disk. The character will be **A**, **B** or **C**, indicating which peg the disk is currently
on. You may assume that the monks’ overall goal is to move the
disks from peg **A** to peg **B**, and that the input represents a legitimate
position in the optimal solution. The input will end with a
line with a single capital **X**.

For each test case, print a single number on its own line indicating the number of moves remaining until the given Towers of Hanoi problem is solved. Output no extra spaces, and do not separate answers with blank lines. All possible inputs yield answers which will fit in a signed $64$-bit integer.

Sample Input 1 | Sample Output 1 |
---|---|

AAA BBB X |
7 0 |