Mitya and the Graph

Time limit2sMemory limit256 MB

Summary

Construct a graph on n vertices with no simple even cycle and the maximum possible number of edges, then print every edge.

Level: Medium7 of 10
Topics: Graph, Math, Greedy, Implementation
Solved: No attempts yet

Problem

Mitya is studying graph theory. He has already studied trees, cactus graphs, complete graphs, and many others. Now he wants to study graphs without simple even cycles. A cycle is simple if it does not pass through any vertex more than once. A cycle is even if it contains an even number of vertices.

Mitya wants to construct such a graph on a given number of vertices so that the number of edges is as large as possible. Help Mitya finish his research.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10\,000$ ).

Output

In the first line, output the number $m$ of edges in a graph that satisfies the condition. The next $m$ lines must contain two integers each, describing an edge of the graph.

Examples1

Example 1
Input
```
3
```
Expected output
```
3
1 2
2 3
3 1
```