하노이 탑 이동 순서

장대 세 개가 있고, 첫 번째 장대에 반지름이 모두 다른 원판 $N$개가 아래에서 위로 큰 것부터 차례로 쌓여 있다. 수도승들이 다음 두 규칙을 지키면서 원판을 모두 세 번째 장대로 옮기려고 한다.

1. 한 번에 원판 한 개만 다른 장대로 옮길 수 있다.
2. 쌓여 있는 원판은 언제나 위쪽 원판이 아래쪽 원판보다 작아야 한다.

이 작업에 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수가 최소여야 한다.

아래 그림은 원판이 5개일 때의 예시이다.

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 $N$이 주어진다. ($1 \le N \le 20$)

첫째 줄에 옮긴 횟수 $K$를 출력한다.

이어지는 $K$개의 줄에 이동 과정을 순서대로 출력한다. 각 줄에는 두 정수 $A$와 $B$를 공백 하나로 구분해 출력하며, 이는 $A$번 장대의 가장 위에 있는 원판을 $B$번 장대의 가장 위로 옮긴다는 뜻이다.

이동 횟수가 최소인 이동 순서는 하나뿐이므로, 정답 출력도 하나로 정해진다.