With the 2008 Beijing Olympics approaching, the organizing committee is struggling to schedule the competitions. We are considering a round-robin tournament format, where every pair of participants plays exactly one match against each other. For convenience, we assume that each participant can play at most one match per day. Due to the unprecedented scale of the 2008 Olympics and the large number of events, the organizing committee hopes to make the tournament schedule as short as possible.

As a volunteer, you have been assigned to solve this problem. Use any method you like, as long as you provide a schedule that completes the tournament as quickly as possible.

Input

The input consists of a single integer $n$, representing the number of participants in the tournament. The specific values of $n$ for the test cases are:

In10: 4, in1: 5, in2: 6, in3: 9, in4: 11, in5: 14, in6: 16, in7: 20, in8: 23, in9: 25.

Output

The first line should output $n$ as it is.

The following lines should represent the daily competition schedule in order. Participants are numbered from $0$ to $n-1$. If participant $i$ and participant $j$ play a match on a given day, output the pair $(i,j)$ on that line, with exactly one space between each pair of parentheses. After all participants playing on that day have been output, if there are any participants who have a bye (are not playing), list them individually at the end of the line, separated by spaces.

For example, if there are six participants in a competition, and on the first day participant $0$ plays $3$, participant $2$ plays $4$, and participants $5$ and $1$ have a bye, it can be represented as: (0,3) (2,4) 5 1

Apart from this, do not leave any extra spaces in the output file.

Examples

Input 1

2

Output 1

2
(0,1)

Input 2

3

Output 2

3
(0,1) 2
(1,2) 0
(2,0) 1