Стало доброй традицией на соревнованиях по программированию решать задачу про Ханойскую башню.

Кратко напомним правила этой игры-головоломки.

Имеются три стержня: $$$A$$$, $$$B$$$, $$$C$$$. Первоначально на исходном стержне $$$A$$$ размещены $$$N$$$ дисков различного диаметра: самый маленький диск наверху, и далее – по возрастанию диаметра. Второй и третий стержни пока пусты.

Требуется переместить все диски с исходного стержня $$$A$$$ на результирующий стержень $$$B$$$, используя третий стержень $$$C$$$ как вспомогательный. За один ход разрешается взять один (обязательно верхний) диск и надеть его на другой стержень, возможно пустой. Причем, диск большего диаметра запрещается класть на диск меньшего размера. Во многих учебниках по программированию приводится процедура решения этой головоломки.

Procedure Hanoi (X, Y, Z: char; N: integer);
Begin
 If N>0 then 
    Begin
       Hanoi (X, Z, Y, N-1);
       Writeln('Disk ', N, ' from ', X, ' to ', Y);
       Hanoi (Z, Y, X, N-1)
    End
End;

Доцент П. из города Р., готовясь к чемпионату по программированию, решил размяться и принялся вручную перекладывать диски Ханойской башни. (Для этого он использовал кольца от детской пирамидки и три стержня, отобранные у внучки.)

В какой-то момент внучка, обидевшись на деда, отобрала часть колец, не тронув только исходный стержень с нанизанными дисками-кольцами.

Помогите доценту и рассчитайте, какое минимально возможное число ходов он успел сделать, если известно текущее расположение дисков на исходном стержне.

Перекладывания дисков выполняются по стандартному алгоритму, описанному в процедуре выше. Комбинация дисков, заданная во входном файле, гарантированно достижима.