Buggy python submission (verdict: Time Limit Exceeded):
import heapq
K=int(input())
G=[[(1,(i+1)%K)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((0,a))
stack=list(G[1])
heapq.heapify(stack)
reached=[0]*K
reached[1]=1
while(stack):
    c,g=heapq.heappop(stack)
    if g==0:
        print(c+1)
        quit()
    reached[g]=1
    for i in G[g]:
        if reached[i[1]]:
            continue
        heapq.heappush(stack,(c+i[0],i[1]))


Fixed submission:
import heapq
K=int(input())
G=[[((i+1)%K,1)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((a,0))
def dijkstra(G,s):#Gはi->jの辺をG[i]=[(j,cost),...]で保存
  INF=10**19
  n=len(G)
  d=[INF]*n#n=node数
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heapq.heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heapq.heappush(que,(d[node],node))
  return d

d=dijkstra(G,1)
print(d[0]+1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
K=int(input())
G=[[(1,(i+1)%K)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((0,a))
stack=list(G[1])
heapq.heapify(stack)
reached=[0]*K
reached[1]=1
while(stack):
    c,g=heapq.heappop(stack)
    if g==0:
        print(c+1)
        quit()
    reached[g]=1
    for i in G[g]:
        if reached[i[1]]:
            continue
        heapq.heappush(stack,(c+i[0],i[1]))


Fixed submission:
import heapq
K=int(input())
G=[[((i+1)%K,1)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((a,0))
def dijkstra(G,s):#Gはi->jの辺をG[i]=[(j,cost),...]で保存
  INF=10**19
  n=len(G)
  d=[INF]*n#n=node数
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heapq.heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heapq.heappush(que,(d[node],node))
  return d

d=dijkstra(G,1)
print(d[0]+1)

Buggy python submission (verdict: Runtime Error):
K=int(input())
G=[[(1,(i+1)%K)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((0,a))
stack=list(G[1])
heapq.heapify(stack)
reached=[0]*K
reached[1]=1
while(stack):
    c,g=heapq.heappop(stack)
    if g==0:
        print(c+1)
        quit()
    reached[g]=1
    for i in G[g]:
        if reached[i[1]]:
            continue
        heapq.heappush(stack,(c+i[0],i[1]))


Fixed submission:
import heapq
K=int(input())
G=[[((i+1)%K,1)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((a,0))
def dijkstra(G,s):#Gはi->jの辺をG[i]=[(j,cost),...]で保存
  INF=10**19
  n=len(G)
  d=[INF]*n#n=node数
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heapq.heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heapq.heappush(que,(d[node],node))
  return d

d=dijkstra(G,1)
print(d[0]+1)

Buggy python submission (verdict: Runtime Error):
from math import log
K=int(input())
N=K
def func(N):
    res=0
    while(N!=0):
        res+=N%10
        N//=10
    return res
ans=func(K)
if ans==1:
    print(ans)
    quit()
n=ceil(log(K,10))
MOD=10**(n)
K=K*(ceil((10**n)/K))
ans=min(ans,func(K))
used=[0]*N
K%=MOD
K*=10
while(True):
    K%=N
    if K==0:
        print(1)
        quit()
    ans=min(ans,func(K)+1)
    if used[K]:
        print(ans)
        quit()
    used[K]=1
    K*=10


Fixed submission:
import heapq
K=int(input())
G=[[((i+1)%K,1)] for i in range(K)]
for i in range(K):
    a=(i*10)%K
    G[i].append((a,0))
def dijkstra(G,s):#Gはi->jの辺をG[i]=[(j,cost),...]で保存
  INF=10**19
  n=len(G)
  d=[INF]*n#n=node数
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heapq.heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heapq.heappush(que,(d[node],node))
  return d

d=dijkstra(G,1)
print(d[0]+1)