Ханойські вежі

Задано три стержня. На першому стержні знаходиться декілька дисків зверху донизу за зростанням розміру диска. Два інші порожні. Потрібно перенести усі диски з першого стержня на другий. Переносити диски дозволяється лише по одному. Не дозволяється класти більший диск на менший.

Вхідні дані

Кількість дисків $n(1\le n\le 19)$ на першому стержні.

Вихідні дані

Виведіть по два числа у рядку — номери стержнів, звідки і куди переноситься диск. Розв'язок повинен бути найкоротшим.

Приклади