하노이 탑

원판이 n개 (1 이상 10 이하) 쌓인 1번 기둥에서 3번 기둥으로 원판을 모두 옮기려 합니다. 한 번에 한 개씩만 옮길 수 있고, 큰 원판을 작은 원판 위에 올릴 수 없습니다.

첫 줄에 옮기는 횟수를 출력하고, 이어서 각 줄에 어느 기둥에서 어느 기둥으로 옮기는지 공백으로 구분해 출력하세요.

옮기는 순서는 원판을 가장 적게 움직이는 방법이어야 합니다.

예시

입력

2

출력

3
1 2
1 3
2 3