Problem K. Keep on doing!

Author:Антон Карабанов   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

The expression n − (n − 1) − (n − 2) − (n − 3) − ...  − 3 − 2 − 1 is written on the board (for example, if n = 5 it will be written as 5 − 4 − 3 − 2 − 1). To avoid a failing grade in mathematics, Gavrila needs to put left and right parentheses in this expression, so that the result is zero. How many ways does he have to do it?

Input format

Input contains natural number n.

Output format

In the first line output a non-negative integer m — the number of ways to arrange the parentheses in the required way. In the next m lines print two space-separated natural numbers a and b — the position of the parentheses (numbers from a to b inclusive will be inside the brackets). Output numbers a and b in descending order, and output pairs of numbers in order of descending a.

Constraints

4 ≤ n ≤ 105

Note on samples

In the first example, n = 5 is given. Unfortunately, Gavrila won't succeed, for the given n there is no way to place the brackets in the required way.

In the second example n = 7 is given. If all numbers from 5 to 3 are enclosed in brackets, then an expression with the desired value will be obtained: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.

In the third example, for n = 12 there are several ways to solve the problem.

Sample tests

No. Standard input Standard output
1
5
0
2
7
1
5 3
3
12
2
11 8
8 2

0.113s 0.017s 15