Од три дата штапа, на једном је \(n\) дискова различитих величина, а остала два су празна. Дискови на првом штапу су поређани по величини, то јест тако да је диск величине \(n\) на дну, на њему је диск величине \(n-1\) итд. све до диска величине 1, који је на врху.

Потребно је дискове преместити са првог на трећи штап користећи што мање премештања. При томе треба премештати дискове један по један и стављати само мањи диск на већи, а никако обрнуто (није дозвољено стављати већи диск преко мањег).

На пример, ако је \(n=3\), редослед премештања треба да буде:

    диск величине 1 са штапа 1 на штап 3
    диск величине 2 са штапа 1 на штап 2
    диск величине 1 са штапа 3 на штап 2
    диск величине 3 са штапа 1 на штап 3
    диск величине 1 са штапа 2 на штап 1
    диск величине 2 са штапа 2 на штап 3
    диск величине 1 са штапа 1 на штап 3

Напиши програм који за дати број дискова \(n\) исписује редослед премештања.

Улаз

Са стандардног улаза се учитава број штапова \(n\) (\(1 \leq n \leq 10\)).

Излаз

На стандардни излаз за свако премештање једног диска исписати по један ред, у коме се наводи редни број штапа са чијег врха се диск премешта и редни број штапа на чији врх се диск премешта, раздвојене једним размаком.

Пример 1

Улаз

3

Излаз

1 3
1 2
3 2
1 3
2 1
2 3
1 3

Пример 2

Улаз

2

Излаз

1 2
1 3
2 3

Овај задатак има и другачија решења у делу збирке који следи.