Стійке дерево

Limits: 2 sec., 512 MiB

Для дерева \(T\) визначимо функцію \(f_T(d)\), яка ставить у відповідність цілому числу \(d\) кількість вершин дерева \(T\) із степенем \(d\). Степінь вершини — це кількість сусідніх вершин до неї.

Стійкістю дерева \(T\) називається мінімальне значення \(f_T(\deg(v))\) серед усіх вершин \(v\) дерева \(T\). \(\deg(v)\) позначає степінь вершини \(v\).

Задано натуральне число \(n\).

Побудуйте дерево з \(n\) вершин з найбільшою стійкістю. Зауважте, що вершини дерева нумеруються з 1.

Input

В одному рядку задано натуральне число \(n\).

Output

У першому рядку виведіть ціле число — найбільшу стійкість дерева.

У наступних \(n - 1\) рядках виведіть по два цілих числа \(u\), \(v\) — номери вершин, з’єднаних ребром у дереві.

Якщо відповідей декілька, виведіть будь-яку.

Constraints

\(2 \le n \le 10^5\).

Samples