\(n\) диск саны берілген. Бастапқыда барлық дискілер бірінші өзекте төменнен жоғары қарай өлшемі кему ретімен орналасқан. Барлық дискілерді бірінші өзектен үшінші өзекке көшіру үшін жүрістер тізбегін шығару керек.

Бір жүрісте тек бір жоғарғы дискіні бір өзектен екінші өзекке көшіруге болады. Үлкен дискіні кіші дискінің үстіне қоюға болмайды.

Енгізу

Жалғыз жолда бүтін \(n\) саны берілген (\(1 \le n \le 20\)).

Шығару

Алдымен жүрістер санын шығарыңыз. Содан кейін әр жүрісті жеке жолға \(a\ b\) форматында шығарыңыз: жоғарғы дискіні \(a\) өзегінен \(b\) өзегіне көшіру.

Мысалдар

Енгізу 1

2

Жауап 1

3
1 2
1 3
2 3

Енгізу 2

3

Жауап 2

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3