하노이 탑

세 개의 장대가 있다. 첫 번째 장대에는 반지름이 모두 다른 원판 N개가 큰 원판이 아래에, 작은 원판이 위에 오도록 쌓여 있다.

다음 규칙을 지키며 모든 원판을 첫 번째 장대에서 세 번째 장대로 옮기려고 한다.

1. 한 번에 원판 한 개만 옮길 수 있다.
2. 큰 원판을 작은 원판 위에 올릴 수 없다.

이동 횟수가 최소가 되도록 원판을 옮기는 순서를 출력하는 프로그램을 작성하라.

아래 그림은 원판이 5개인 경우를 보여 준다.

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N이 주어진다. (1 <= N <= 100)

첫째 줄에 최소 이동 횟수 K를 출력한다.

N이 20 이하이면 둘째 줄부터 이동 과정을 출력한다. 이어지는 K개의 줄에는 두 정수 A와 B를 공백으로 구분해 출력한다. 이는 A번 장대의 가장 위에 있는 원판을 B번 장대로 옮긴다는 뜻이다.

N이 20보다 크면 이동 과정은 출력하지 않아도 된다.