Stable Tree

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

For a tree \(T\), let us define a function \(f_T(d)\) which associates an integer \(d\) with the number of vertices in tree \(T\) that have degree \(d\). The degree of a vertex is the number of vertices adjacent to it.

The stability of a tree \(T\) is defined as the minimum value of \(f_T(\deg(v))\) among all vertices \(v\) of the tree \(T\). \(\deg(v)\) denotes the degree of vertex \(v\).

You are given a positive integer \(n\).

Construct a tree with \(n\) vertices having the maximum possible stability. Note that the vertices of the tree are numbered from 1.

Input

A single line contains a positive integer \(n\).

Output

In the first line, print an integer — the maximum stability of the tree.

In the next \(n - 1\) lines, print two integers \(u\), \(v\) — the numbers of the vertices connected by an edge in the tree.

If there are multiple answers, print any of them.

Constraints

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

Samples