Problem description

Za górami, za lasami, w odległym Tybecie buddyjscy mnisi zajmują się sprawami, które wpływają na bieg wszechrzeczy. Głównym obiektem ich zainteresowania są złote krążki nanizane na diamentowe pręty.

Mamy trzy pręty i N krążków różnych rozmiarów nanizanych na pierwszy pręt. Krążki są ułożone od największego do najmniejszego (patrząc od dołu do góry).

Chcemy przenieść wszystkie krążki z pierwszego pręta na drugi, być może używając trzeciego i przestrzegając następujących reguł:

• w pojedynczym ruchu można przełożyć tylko jeden krążek;
• nigdy nie kładziemy większego krążka na mniejszy.

Napisz program, który dla danego N wyznaczy najkrótszą sekwencję ruchów, która prowadzi do rozwiązania powyższego problemu.

Wejście

W pierwszym wierszu wejścia znajdują się liczba naturalna N oznaczająca liczbę krążków, które chcemy przenieść.

Wyjście

Na wyjściu powinna zostać wypisana najkrótsza sekwencja ruchów prowadząca do przeniesienia krążków z pierwszego pręta na drugi. W i-tym wierszu powinny znaleźć się dwie liczby a_i, b_i oddzielone spacją, oznaczające, że w i-tym ruchu przekładamy krążek z pręta a_i na pręt b_i.

Ograniczenia

1 ≤ N ≤ 20.

Przykład

2

1 3
1 2
3 2