D. Divisibility Trick
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Dmitry has recently learned a simple rule to check if an integer is divisible by 3. An integer is divisible by 3 if the sum of its digits is divisible by 3.

Later he also learned that the same rule can be used to check if an integer is divisible by 9. An integer is divisible by 9 if the sum of its digits is divisible by 9.

Dmitry's elder sister Daria wants to trick him by showing that the same rule can be applied to any divisor $$$d$$$. To do this, she wants to show Dmitry an example of a positive integer $$$n$$$ such that $$$n$$$ is divisible by $$$d$$$, and the sum of the digits of $$$n$$$ is also divisible by $$$d$$$. Help her to find such a number.

Input

The only line contains a single integer $$$d$$$ ($$$1\le d\le 1000$$$).

Output

Print a positive integer $$$n$$$ divisible by $$$d$$$ such that the sum of its digits is also divisible by $$$d$$$.

The value of $$$n$$$ must consist of at most $$$10^6$$$ digits and must not have leading zeroes. It can be shown that such an integer always exists. If there are multiple answers, print any of them.

Examples
Input
3
Output
3
Input
13
Output
1898
Input
1
Output
239
Note

In the first example, $$$3$$$ is divisible by $$$3$$$, and its sum of digits, $$$3$$$, is also divisible by $$$3$$$.

In the second example, $$$1898$$$ is divisible by $$$13$$$, and its sum of digits, $$$1 + 8 + 9 + 8 = 26$$$, is also divisible by $$$13$$$.

In the third example, any positive integer satisfies the conditions.