Description

You have a multiset. Initially, it contains only one positive integer $n$.

Each time, you may choose a positive integer $x$ currently in the multiset and remove it, then specify a positive integer $y$ (it does not need to be in the multiset) such that $x>y$, and insert $y$ and $x-y$ into the multiset.

You must ensure that at any moment, the maximum value in the multiset is strictly less than $2$ times the minimum value in the multiset.

Find the maximum number of operations you can perform, and output a construction.

The input guarantees that the maximum number of operations does not exceed $10^6$.

Input Format

A single line containing one integer $n$.

Output Format

The first line contains one integer $m$, the number of operations in your constructed plan.

The next $m$ lines each contain two integers $x,y$, describing one operation (the meanings of $x,y$ are the same as in the statement).

You must ensure that $x>y$ and that $x$ has appeared in the current multiset.

8

2
8 3
5 2

30

5
30 12
18 8
12 6
10 5
8 4

Hint

For $100\%$ of the testdata, $1\le n\le 10^9$.

Constraints

Scoring

In the following cases, you will get $0$ points on that test point:

• The output format does not meet the requirements.

• Extra information is printed (including spaces and newline characters).

• The number of operations in your construction is different from the standard answer.

• Your construction does not satisfy the requirements of the problem.

• Time limit exceeded.

If none of the above happens, you will get full score on that test point.

It is guaranteed that the SPJ uses no more than $100\operatorname{ms},10\operatorname{MB}$.

Sample Explanation 1

One possible sequence of operations is as follows:

8

3 5

2 3 3

It can be proven that there is no better plan.

Sample Explanation 2

One possible sequence of operations is as follows:

30

12 18

8 10 12

6 6 8 10

5 5 6 6 8

4 4 5 5 6 6

It can be proven that there is no better plan.

Translated by ChatGPT 5