Title
Problem Statement
Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K.
Constraints
- 2 ≤ K ≤ 106
- K is an integer.
Subtasks
- Subtask 1: 2 ≤ K ≤ 103
- Subtask 2: 2 ≤ K ≤ 106
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