Problem Statement

Output one graph satisfying the following conditions. (What even is an Array...)

• It is a directed graph with $N$ vertices and $M$ edges, where edge $i$ ($1 \leq i \leq M$) goes from vertex $d1_i$ to vertex $d2_i$. It must satisfy $d1_i < d2_i$.
• The number of ways to go from vertex $1$ to vertex $N$ (the number of paths starting at vertex $1$ and ending at vertex $N$) is exactly $K$.
• It must satisfy $1 \leq N \leq 32$. Also, if $i \neq j$, at least one of $d1_i \neq d1_j$ and $d2_i \neq d2_j$ must hold.

Input

K

An integer $K$ between $0$ and $10^{9}$, inclusive, is given on $1$ line.

Output

$N$ $M$
$d1_1$ $d2_1$
$d1_2$ $d2_2$
...
$d1_M$ $d2_M$

On line $1$, output the number of vertices $N$ and the number of edges $M$ of the graph.
On the $M$ lines starting from line $2$, output the information of the edges of the graph.
Print a newline at the end.

Sample

2

3 3
1 2
1 3
2 3

3

5 6
1 2
2 3
3 4
4 5
1 5
2 4

12

9 15
1 2
1 3
2 3
2 4
2 8
3 5
4 6
4 7
5 6
5 7
5 8
6 8
6 9
7 9
8 9