### ** multiple**

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