Гра Ханойська вежа складається з трьох стопок (лівої, середньої та правої) і ~n~ круглих дисків різного розміру. Спочатку лівий стек містить усі диски в порядку збільшення розміру зверху вниз.

Мета полягає в тому, щоб перемістити всі диски в правий стек за допомогою середнього стека. Під час кожного ходу ви можете переміщати найвищий диск із стопки в іншу. Крім того, не дозволяється розміщувати більший диск на меншому.

Ваше завдання - знайти рішення, яке мінімізує кількість ходів.

Обмеження

• ~1 \le n \le 16~

Формат вхідних даних

Єдиний рядок введення містить ціле число ~n~: кількість дисків.

Формат вихідних даних

Спочатку вивести ціле число ~k~: мінімальна кількість ходів.

Після цього виведіть ~k~ рядків, які описують ходи. У кожному рядку є два цілих числа ~a~ і ~b~: ви переміщуєте диск зі стека ~a~ в стек ~b~.

Приклад вхідних даних

2

Приклад вихідних даних

3
1 2
1 3
2 3