11729번

x = int(input())

def hanoi(x, start, end):
  if x == 1:
    print(start, end)
    return

  hanoi(x - 1, start, 6-start-end)
  print(start, end)
  hanoi(x-1, 6-start-end, end)

print(2**x-1)
hanoi(x, 1, 3)

start와 end 기둥을 알면 마지막 기둥의 번호도 알아낼 수 있음