A directed acyclic graph (DAG) is, as the name suggests, a directed graph that contains no cycles.

If we choose two vertices in such a graph, we can calculate how many different directed paths exist between these vertices. We consider two such paths to be different if one of them traverses an edge that the other does not.

Your task is to create a directed acyclic graph with $n$ vertices (numbered from 1 to $n$), in which there are exactly $k$ paths from vertex 1 to vertex $n$. However, there are a few catches. Your graph can have at most 100 vertices, each vertex can have at most two outgoing edges, and it cannot contain multi-edges (i.e., if two edges leave a vertex, they must lead to different vertices). It can be proven that for every possible $k$ satisfying the constraints given below, it is possible to construct a graph that meets these conditions.

Input

The first and only line of input contains a single integer $k$ ($1 \le k \le 10^9$).

Output

The first line of output should contain a single integer $n$ ($2 \le n \le 100$) representing the number of vertices in your graph.

In the next $n$ lines, there should be two integers each. The numbers in the $i$-th line should indicate the vertices to which the edges originating from vertex $i$ lead. Any of these numbers can be equal to $-1$ if you want the given edge not to exist. If both numbers in a line are different from $-1$, they must be different from each other.

If there are multiple graphs satisfying the problem conditions, you may output any one of them. Note that you do not need to minimize the number of vertices in the graph; it is sufficient to stay within the limit on their number.

Examples

Input 1

3

Output 1

6
3 5
6 -1
2 6
2 6
6 -1
-1 -1

Note

The following figure shows the 6-vertex graph described in the output. From vertex 1 to vertex 6, there are paths $1 \to 3 \to 2 \to 6$, $1 \to 3 \to 6$, and $1 \to 5 \to 6$.