하노이탑

문제 정의

세 개의 기둥 A, B, C와 크기가 서로 다른 n
개의 고리가 A 기둥에 크기가 작은 고리가 위에 있도록 꽂혀 있습니다. A 기둥에 있는 n

개의 고리들을 아래의 두 조건을 만족하면서 C 기둥으로 전부 옮기는 작업을 하려고 합니다.
한 번 옮길 때 하나의 고리만 움직일 수 있습니다.
큰 원판은 작은 원판 위에 있을 수 없습니다.

여러 방법이 있을 수 있으나, 2n−1
번 만에 A 기둥의 고리들을 C 기둥으로 옮길 수 있다는 사실이 잘 알려져 있습니다. A 기둥의 고리들을 어떻게 옮기면 C 기둥으로 2n−1

번 만에 옮길 수 있는 지 경로를 출력하는 프로그램을 작성하세요.

입력 형식

입력의 첫 줄에 테스트 케이스의 숫자 t가 주어진다.
그 후, t줄에 걸쳐 테스트 케이스마다 고리의 수 n이 주어진다. n은 10 이하의 자연수이다.

출력 형식

각 테스트 케이스에서 입력 받은 n에 대해서, A에서 C기둥으로 고리가 옮겨가는 과정을 한 줄에 하나씩 출력한다. 출력 형식은 '고리가 있는 기둥 -> 옮길 기둥'이다. 예를 들어 A의 가장 위에 있는 고리가 B로 옮겨간다면 'A -> B'를 출력한다. 출력 시 기둥을 나타내는 알파벳과 화살표 기호 사이에 띄어쓰기가 있음을 유의한다. (A -> B O , A->B X)

입력 예시

2
2
3

출력 예시

A -> B
A -> C
B -> C
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

t = int(input())

def hanoi1(n, A, C, B): #num,from, to, other
    if n == 0:
        return
    hanoi1(n-1, A, B, C)
    # print('a')
    print(A + '->' + C)
    hanoi1(n-1, B, C, A)

for _ in range(t):
    n = int(input())
    hanoi1(n, 'A', 'C', 'B')