Problem Statement

A tree with at most $2\times 10^5$ vertices, in which each vertex is either brown or green, is called a good branch if it satisfies all of the following conditions.

• There exists a brown vertex.
• There exists a green vertex.
• Each brown vertex is adjacent to at most $2$ brown vertices.
• No path connecting two brown vertices contains a green vertex.

The beauty of a good branch is determined as follows.

• For every brown vertex, find the number of green vertices adjacent to it.
• The beauty is the product of all these numbers.

Output a good branch whose beauty is exactly $X$ and whose number of vertices is the minimum among such good branches. If there are multiple such good branches, you may output any of them.

If no good branch satisfies the condition, report that instead. In particular, note that a tree with more than $\mathbf{2\times 10^5}$ vertices does not satisfy the conditions of a good branch.

Constraints

• $1\leq X\leq 10^{18}$
• $X$ is an integer.

Input

The input is given from standard input in the following format.

$X$

Output

If no good branch satisfies the condition, output only -1.

Otherwise, that is, if an answer exists, output in the following format.

$n$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{n-1}\ v_{n-1}$
$c_1\ c_2\dots c_n$

Here, $n$ is the number of vertices. You are to output a tree whose vertices are numbered $1,2,\dots,n$.

$u_i\ v_i$ denotes an edge connecting vertex $u_i$ and vertex $v_i$, and $c_i$ denotes the color of vertex $i$. Here, $c_i$ must be b or g: $c_i=$ b means that vertex $i$ is brown, and $c_i=$ g means that vertex $i$ is green.

If your output does not follow this format, the verdict is undefined. In particular, if there are extra line breaks or spaces, or if required line breaks or spaces are missing, it may be judged as WA.

Sample

Sample 1

Input

1

Output

2
1 2
b g

This output represents the following tree, where vertex $1$ is painted brown and vertex $2$ is painted green.

We can verify that this tree satisfies all the conditions of a good branch. Vertex $1$ is adjacent to $1$ green vertex, so the beauty is $1$. No tree with $1$ or fewer vertices satisfies the conditions, so this is a correct answer.

For example, the following output has beauty $1$, but it is judged as incorrect because its number of vertices is not the minimum.

3
1 2
2 3
b g g

Sample 2

Input

10

Output

9
1 2
2 3
4 2
5 4
7 4
4 6
9 4
4 8
g b g b g g g g g

This output represents the following tree, where vertices $2,4$ are painted brown and the others are painted green.

We can verify that this tree satisfies all the conditions of a good branch. Vertex $2$ is adjacent to $2$ green vertices and vertex $4$ is adjacent to $5$ green vertices, so the beauty is $10$. No tree with $8$ or fewer vertices satisfies the conditions, so this is a correct answer.

998244353

-1