We have a complete undirected graph of size $n$: for all pairs of vertices $(u, v)$ such that $1 \le u < v \le n$, there exists an edge between $u$ and $v$. Find a way to represent the set of edges in this graph as a union of several $n$-vertex trees.

Let $k$ be the number of trees, and $T_1, \ldots, T_k$ be the trees. Then:

• Each $T_i$ should be a tree with $n$ vertices numbered from $1$ to $n$ and $n - 1$ edges.
• The union of all edges of all trees should form a complete graph.
• The number of trees $k$ should be the minimum possible.

Input

The first line contains an integer $n$, the size of the graph ($2 \le n \le 1000$).

Output

On the first line, print $k$, the number of trees. The number $k$ should be the minimum possible. After that, print the $k$ trees, one after another, without empty lines.

For each tree, print $n - 1$ lines denoting its edges. For each edge, print a line with two integers $u$ and $v$: the vertices connected by this edge.

If there are several optimal answers, print any one of them.

Examples

Input 1

2

Output 1

1
1 2

Input 2

3

Output 2

2
1 2
1 3
1 3
2 3