#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Title

### Problem Statement

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

### Constraints

`2 ≤ K ≤ 10`^{6}`K`is an integer.

### Subtasks

- Subtask 1:
`2 ≤ K ≤ 10`^{3} - Subtask 2:
`2 ≤ K ≤ 10`^{6}

### 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 1

6

### Sample Output 1

3

`12=6×2` yields the smallest sum.

### Sample Input 2

41

### Sample Output 2

5

`11111=41×271` yields the smallest sum.

### Sample Input 3

79992

### Sample Output 3

36

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 30 | 20 | 1s | 256MB | Minimum |

2 | 70 | 87 | 1s | 256MB | Minimum |

3 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o multiple -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512