subway

Antonia recently visited London. There, she was impressed by the large number of subway stations, which, to her surprise, formed a tree. While getting bored on the subway, Antonia wondered if she could generate a tree with the minimum number of nodes that would have exactly $K$ paths from $X$ to $Y$, for any nodes $X$, $Y$, provided that $X$ is an ancestor of $Y$. By replacing the current subway map with this tree, she believes it could reduce rush-hour congestion.

Task

Help Antonia generate the desired tree with the minimum number of nodes.

Input data

The input will contain a single integer number, $K$ – the number of pairs with the specified property.

Output data

The output will contain $N+1$ lines, representing the generated tree, the nodes being indexed from $0$.

The first line will contain the number $N$ – the number of nodes in the tree.

The following $N$ lines will contain each 2 numbers $X$ and $T$, separated by a space, with the following meaning: node $T$ is the direct ancestor of node $X$. If node $X$ doesn’t have a direct ancestor, $T$ will have value $-1$.

Constraints and clarifications

• For each test, the tree must have at most $10^6$ nodes.
• $0 \leq K \leq 10^9$
• For every test, you will get:
  1. $100\%$ points if $N_{\text{participant}} = N_{\text{committee}}$
  2. $80\%$ points if $N_{\text{participant}} \in [N_{\text{committee}} + 1, N_{\text{committee}} + 2]$
  3. $P\%$ points if $N_{\text{participant}} \geq N_{\text{committee}} + 3$, where $P = \frac{N_{\text{committee}} + 3}{N_{\text{participant}}} \cdot 50$
• Note: $N_{\text{committee}}$ is the minimum number of nodes that a tree with the specified property can be generated with.

Example 1

stdin

2

stdout

3
0 -1
1 0
2 0

Explanation

There are $2$ pairs $(X, Y)$, such that $X$ is the ancestor of $Y$:

$(X,Y) \in \{(0, 1), (0, 2)\}$

Example 2

stdin

4

stdout

4
0 -1
1 0
2 0
3 2

Explanation

There are $4$ pairs $(X, Y)$, such that $X$ is the ancestor of $Y$:

$(X,Y) \in \{(0, 1), (0, 2), (0, 3), (2, 3)\}$