세 개의 기둥 A, B, C가 있고, A 기둥에는 크기가 서로 다른 원반 \(N\)개가 작은 것이 위로 오도록 순서대로 쌓여 있다.

다음 규칙을 지키면서 A 기둥에 있는 원반 \(N\)개를 모두 C 기둥으로 옮기려고 한다.

• 한 번에 하나의 원반만 옮길 수 있다.
• 각 기둥의 맨 위에 있는 원반만 옮길 수 있다.
• 더 작은 원반 위에 더 큰 원반을 올려놓을 수 없다.

최소 횟수로 옮길 때, 그 이동 순서를 출력하시오.

입력

첫째 줄에 원반의 개수 \(N\)이 주어진다.

• \(1 \le N \le 20\)

출력

원반을 옮기는 순서대로, 한 줄에 하나씩 출발 기둥과 도착 기둥을 공백으로 구분하여 출력한다.

출력하는 줄의 수는 항상 \(2^N - 1\)이다.

예제 입력 1

2

예제 출력 1

A B
A C
B C

예제 입력 2

3

예제 출력 2

A C
A B
C B
A C
B A
B C
A C