Given a positive integer $N$, find the smallest positive integer whose sum of digits equals $N$.

Input

• A positive integer $N$ ($1\le N\le {10}^7$).

Output

• The smallest positive integer whose sum of digits equals $N$.

Sample Input

10

Sample Output

19