Maximum Operations on a Constrained Multiset

You are given a multiset that initially contains a single positive integer \(n\). In one operation you may do the following:

• Choose a number \(x\) from the multiset (\(x>0\)) and remove it.
• Choose a positive integer \(y\) (not necessarily in the multiset) with \(x>y\), and then add both \(y\) and \(x-y\) into the multiset.

However, you must maintain the following invariant at every moment (before and after every operation):

[ \max(S) < 2\cdot \min(S), ]

where \(S\) is the current multiset, \(\min(S)\) denotes its smallest element, and \(\max(S)\) its largest element.

An operation is valid if after splitting \(x\) into \(y\) and \(x-y\) the invariant still holds. It turns out that one can prove that if an operation on a number \(x\) is valid then a necessary and sufficient condition is that there exists an integer \(a\) such that

[ \frac{x}{3} < a \le \frac{x}{2}, ]

and if you choose \(y=a\) (and hence \(x-y=x-a\)) then the invariant will be maintained. For example, splitting \(8\) into \(3\) and \(5\) is valid because \(8/3 \approx 2.67 < 3 \le 4=8/2\) and in the resulting multiset the minimum becomes \(3\) and the maximum \(5\) so that \(5 < 2\cdot3=6\). (Note that splitting \(8\) as \(4\) and \(4\) would also satisfy \(4 \leq 4\), but this choice might prevent further operations.)

Your task is to perform a sequence of operations (each obeying the invariant) in order to maximize the number of operations you can do. You should output the maximum number of operations as well as a constructive sequence of moves that achieves that number. It is guaranteed that the maximum number of operations does not exceed \(10^6\).

inputFormat

The input consists of a single line containing one integer \(n\) \( (1 \le n \le 10^9)\).

outputFormat

On the first line output an integer \(m\) — the maximum number of valid operations. Then output \(m\) lines, each describing one operation. In each of these lines output two integers \(x\) and \(y\) denoting that in this move you removed \(x\) from the multiset and replaced it with \(y\) and \(x-y\). The operations must be performed in the given order and the moves must satisfy the invariant after each operation.

sample

2

1
2 1