Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

-----Constraints-----
- $2 \leq K \leq 10^5$
- K is an integer.

-----Input-----
Input is given from Standard Input in the following format:
K

-----Output-----
Print the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

-----Sample Input-----
6

-----Sample Output-----
3

12=6×2 yields the smallest sum.

见题面

见题面