The End of the World

Legend says there is a group of monks solving a giant Towers of Hanoi puzzle. The Towers of Hanoi is a well-known puzzle consisting of three pegs and a stack of disks, each a different size. At the start, all of the disks are stacked on one peg, ordered from largest at the bottom to smallest at the top. The goal is to move the entire stack to another peg while obeying two rules:

1. You may move only one disk at a time.
2. You may never place a disk on top of a smaller disk.

The monks believe that when they finish, the world will end. Suppose you know how far they have gotten. Assuming the monks are following the most efficient (fewest-moves) solution, how much time does the world have left?

The input contains several test cases. Each test case is a single line holding a string of length 1 to 63 made up only of the capital letters A, B, and C. The length of the string is the number of disks, and each character gives the current position of one disk. The first character is the position of the smallest disk, the second character is the position of the second-smallest disk, and so on, with the last character giving the position of the largest disk. Each character is A, B, or C, indicating the peg the disk currently rests on. The monks' overall goal is to move every disk from peg A to peg B, and the input is guaranteed to be a legitimate state that actually occurs during the optimal (fewest-moves) solution. The input ends with a line containing a single capital X.

For each test case, print on its own line the number of moves remaining until the given Towers of Hanoi puzzle is solved. Print no extra spaces, and do not separate answers with blank lines. Every possible answer fits in a signed 64-bit integer.