def hanoi(n, A, B, C):
    if n == 1:
        return [(A, C)]
    else:
        return hanoi(n-1, A, C, B) + hanoi(1, A, B, C) + hanoi(n-1, B, A, C)
        # A -> B, A -> C, B -> C
n = input("請輸入整數：")
times = 0
for move in hanoi(int(n), 'A', 'B', 'C'):
    print("盤由 %c 移至 %c" % move)
    times += 1
print("共移動 %d 次" % times)