Decomposition Sum

Interview

Time limit2sMemory limit192 MB

Summary

Given N up to 1,000,000, find the smallest number M such that M plus its digit sum equals N, or print 0 if none exists.

Level: Easy3 of 10
Topics: Brute force, Math, Implementation
Solved: No attempts yet

Problem

The decomposition sum of a natural number N is N plus the sum of its decimal digits. If the decomposition sum of a natural number M is N, then M is called a constructor of N. For example, the decomposition sum of 245 is 245 + 2 + 4 + 5 = 256, so 245 is a constructor of 256. Some natural numbers have no constructor, and some have more than one.

Given a natural number N, write a program that finds the smallest constructor of N.

Input

The first line contains a natural number N (1 <= N <= 1,000,000).

Output

Print the answer on the first line. If N has no constructor, print 0.

Examples1

Example 1
Input
```
216
```
Expected output
```
198
```