p03558 AtCoder Beginner Contest 077 - Small Multiple
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.

Examples

Input

6


Output

3


Input

41


Output

5


Input

79992


Output

36
```python
from collections import deque
k = int(input())
d = deque()
mat = []
for i in range(k):
    mat.append([])
#mark = [False]*k
dis = [10**18]*k
dis[1] = 0
for i in range(k):
    mat[i].append(((i+1)%k,True))

    if (10*i)%k != i:
        mat[i].append(((10*i)%k,False))

#bfs 1->0
d.append(1)
res = 0
while d:
    left = d.popleft()
    for neighbour,edge in mat[left]:
        distance = edge + dis[left]
        if dis[neighbour] > distance: 
            dis[neighbour] = distance 
            
            if edge == 0:
                d.appendleft(neighbour)
            else:
                d.append(neighbour)
print(dis[0]+1) 


```