Buggy python submission (verdict: Time Limit Exceeded):
import sys
# import math
# import queue
# import copy
# import bisect#2分探索


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.insert(0,s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)


Fixed submission:
import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
# import math
# import queue
# import copy
# import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.insert(0,s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)


Fixed submission:
import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
# import math
# import queue
# import copy
# import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())
def inputl():
    return list(map(int, input().split()))
def printl(li):
    print(*li, sep="\n")
def argsort(s):
    return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = inputi()
#N, K = inputl()
#L = [int(input()) for i in range(N)]
#A = inputl()
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)


#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.insert(0,s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)


Fixed submission:
import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)

Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
import queue
import copy
import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())
def inputl():
    return list(map(int, input().split()))
def printl(li):
    print(*li, sep="\n")
def argsort(s):
    return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = inputi()
#N, K = inputl()
#L = [int(input()) for i in range(N)]
#A = inputl()
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)


#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.insert(0,s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)


Fixed submission:
import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)