Since you are madly in love with Larry, you want to give him a present for his birthday. You know that Larry loves graphs and the number ~3~ and decided that you will give him a present that will satisfy both of those desires. You have ~N~ nodes, and want to construct an undirected simple graph for Larry that has ~3~ properties:

• The minimum degree is ~3~
• Adding any edge that is not already part of the graph completes a cycle of length ~3~
• There is no cycle of length ~3~ in the graph itself

Since edges are expensive, you want to find an undirected simple graph with the least number of edges that satisfies these properties. Can you make the perfect gift?

Input Specification

On the only line of input is one integer ~N\ (6 \leq N \leq 100)~, the number of nodes you have.

Output Specification

The first line of output contains one integer ~M~, the number of edges you must use.

The next ~M~ lines contain two integers ~a~ and ~b~ indicating that there is an edge connecting ~a~ and ~b~.

Any optimal output will be accepted.

Subtasks

Subtask 1 (10%)

~N \leq 8~

Subtask 2 (90%)

No further constraints.

Sample Input

6

Sample Output

9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6