Math - MarisaOJ: Marisa Online Judge

Math

Time limit: 1000 ms
Memory limit: 256 MB
Let $f(x)$ be the sum of the digits in the integer $x$. Given an integer $k$, find the smallest $f(x)$ such that $x$ is a positive integer divisible by $k$. ### Input - A single line contains an integer $k$. ### Output - Print the smallest $f(x)$. ### Constraints - $2 \le k \le 10^5$. ### Example Input: ``` 6 ``` Output: ``` 3 ``` #### Note: Choose $x=12$.