Remote Training on Programming

 
Ханойская башня

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

Входные данные
Во входном файле записано одно число N (1<=N<=10)

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

Пример входного файла
2

Пример выходного файла
1 3
1 2
3 2