Всем хорошо известна древняя головоломка. Есть три стержня. На первом из них изначально надето N дисков, причем их размер увеличивается сверху вниз. За один ход можно взять верхний диск с любого стержня и переложить его на любой другой стержень, при этом запрещается класть диски большего размера на диски меньшего. Требуется переложить все диски на второй стержень.
Входные данные. Во входном файле записано число N (1≤N≤15) - количество дисков.
Выходные данные. В выходной файл выведите последовательность операций для решения головоломки. Каждая операция определяется двумя числами - номером стержня, с которого мы снимаем диск и номер стержня, на который мы его помещаем.
| Пример ввода | Пример вывода |
1 | 1 2 |
2 | 1 3 1 2 3 2 |