Christmas Lights Assemby
Peter bought Christmas lights in a do-it-yourself assembly kit.
The box contains:
2·N differently colored light bulbs, no two bulbs are the same color;
2·N sockets for the bulbs;
enough wires to connect the sockets and bulbs to the electric network.
Each socket has a number of slots for connecting wires. The box comes with N types of sockets. The first type has one slot, the second type has two slots, the third has three, … , and so on. The N type has N slots. There are two sockets of each type.
The Christmas lights works when bulbs are screwed into sockets and sockets are wired so that the following conditions are met:
all slots of all sockets must be wired;
one slot may contain only one wire;
each wire must be connected to two different sockets;
two sockets may not be connected by more than one wire.
This task is too difficult for Peter. Help Peter make his Christmas lights work.
Input
The input file contains an integer N — the number of socket types (1 ≤ N ≤ 500).
Output
The first line of the output file must contain an integer M — the number of wires necessary to assemble the kit. The following M lines must each contain two integers separated by spaces ― the numbers of light bulbs screwed into sockets connected by a single wire. The bulbs are numbered from 1 to 2·N. If more than one solution is possible, output any.