Note

Problem I is a problem that asks you to implement part of the judge for this problem.

Problem Statement

Output $1$ positive multiple of $N$ that is a palindrome.

It can be proved that, under the constraints of this problem, at least $1$ such integer that also satisfies the output format below exists.

Constraints

• $1\leq N \leq 10^{12}$

• $N$ is an integer that is not a multiple of $10$.

Input

$N$

Output

If the answer has a repeating structure, it can be output even if it has a huge number of digits. If the decimal representation of the answer integer, viewed as a string, can be expressed as "$S_1$ repeated $T_1$ times" → "$S_2$ repeated $T_2$ times" → $\cdots$ → "$S_K$ repeated $T_K$ times", output it in the following format:

$K$
$S_1$ $T_1$
$\vdots$
$S_K$ $T_K$

Here, each $T_i$ must be at most $10^{18}$, and the total number of characters in the $S_i$ must be at most $2\times 10^5$. Formally, all of the following conditions must be satisfied.

• $1 \leq K\leq 2 \times 10^5$

• $S_i$ $(1\leq i \leq K)$ is a string consisting of the digits 0123456789.

• The first character of $S_1$ is not 0.

• $1 \leq |S_i| \leq 2 \times 10^5$ $(1\leq i \leq K)$

• $\sum_{i = 1}^K |S_i| \leq 2\times 10^5$

• $1 \leq T_i \leq 10^{18}$ $(1\leq i \leq K)$

• $K, T_i$ are integers. $(1\leq i \leq K)$

The sample input and output may be helpful.

Note

This problem uses a special judge. There may be multiple solutions. The behavior of the judge on submissions that do not satisfy the output format is undefined.

Sample

23

1
161 1

3
1 1
3 4
1 1

1
133331 1

4

1
4 1

1
4 1000000000000000000

829

1
15751 1