424. Beautiful graph

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Misha is currently interested in undirected graphs that contain no two simple cycles sharing exactly one edge and contains no loops. Let's call them beautiful graphs. He wants to find the maximal beatiful graph, that is the beautiful graph that contains the most edges among all beautiful graphs with at most n vertices. But Misha is going to leave on vacation, so he asked you to help him with this problem.

Input
The input file contains a single integer n (1 ≤ n ≤ 100) — the maximum number of vertices your graph can contain.

Output
Output the number of vertices V (1 ≤ V ≤ n) and the number of edges E of your graph to the first line of the output file, separated with a space. Then output E lines with two integer numbers each, again separated with a space. The two numbers should be the numbers of the vertices connected by the corresponding edge. The vertices of the graph are numbered from 1 to V. You can output edges in any order. If there are several maximal graphs, output any.

Example(s)
sample input
 
sample output
 
1

1 0


sample input
 
sample output
 
2

2 1
1 2


sample input
 
sample output
 
3

3 3
1 2
2 3
1 3