A number $N$ is called special iff it can be written as $$ N = \mathrm{reverse}(N_1) + N_1 = \mathrm{reverse}(N_2) + N_2, $$ where $N_1$ and $N_2$ are some positive integers and their number of digits (lengths) are different.

For example, $121$ is a special number since $$ \begin{aligned} 121 &= \mathrm{reverse}(74) + 74 = \mathrm{reverse}(110) + 110 \\ &= 47 + 74 = 11 + 110. \end{aligned} $$

There are only two special number less than $10,000$.

Find the first 5,000 smallest special numbers.

Input

This problem has no input data.

Output

Output the first 5,000 special numbers in ascending order. (One special number per one line.)

Example

Output:

121
1111
...
[4998 lines]
...

Information

Source Limit is 10 KB.