Задача "Ханойские башни"

Всем хорошо известна древняя головоломка. Есть три стержня. На первом из них изначально надето N дисков, причем их размер увеличивается сверху вниз. За один ход можно взять верхний диск с любого стержня и переложить его на любой другой стержень, при этом запрещается класть диски большего размера на диски меньшего. Требуется переложить все диски на второй стержень.

Входные данные. Во входном файле записано число N (1≤N≤15) - количество дисков.

Выходные данные. В выходной файл выведите последовательность операций для решения головоломки. Каждая операция определяется двумя числами - номером стержня, с которого мы снимаем диск и номер стержня, на который мы его помещаем.

Пример вводаПример вывода
1
1 2
2
1 3
1 2
3 2