local mmi, mma = math.min, math.max
local mfl = math.floor
local TranFFT = {}

TranFFT.initialize = function(self)
  self.size = 18
  -- 2^18
  self.n = 262144
  -- 1007681537: prime,
  -- 1007681537 % 262144 = 1
  self.mod = 1007681537
  -- (6161^262144) % mod = 1
  self.w = 6161
  -- (1007677693 * 262144) % mod = 1, (1007677693 * 131072) % mod ~= 1
  self.ninv = 1007677693
  -- (534835031 * 6161) % mod = 1
  self.winv = 534835031
  self.p2 = {1}
  for i = 2, self.size do
    self.p2[i] = self.p2[i - 1] * 2
  end
  self.binv = {}
  for i = 1, self.n do
    local y, z = 0, i - 1
    for j = 1, self.size do
      y = y + (z % 2) * self.p2[self.size + 1 - j]
      z = mfl(z / 2)
    end
    self.binv[i] = y + 1
  end
  self.wmul = {1}
  for i = 2, self.n do
    self.wmul[i] = self:mul(self.wmul[i - 1], self.w)
  end
  self.winvmul = {1}
  for i = 2, self.n do
    self.winvmul[i] = self:mul(self.winvmul[i - 1], self.winv)
  end
end

-- (44893^2) % 1007681537 = 18375
-- 1007681537 = 22446 * 44893 + rem(13259)
-- x0, y0 <= 44892
-- x1, y1 <= 22446
-- max(x1y1*18375+(x1y0+x0y1)*44893+x0y0) < 10^14
TranFFT.mul = function(self, x, y)
  local x0, y0 = x % 44893, y % 44893
  local x1, y1 = mfl(x / 44893), mfl(y / 44893)
  return (x1 * y1 * 18375 + (x1 * y0 + x0 * y1) * 44893 + x0 * y0) % self.mod
end

TranFFT.add = function(self, x, y) return (x + y) % self.mod end

TranFFT.fft_common = function(self, ary, wmul)
  local ret = {}
  for i = 1, self.n do
    ret[i] = ary[self.binv[i]]
  end
  for i = 1, self.size do
    local step_size = self.p2[i]
    local step_count = self.p2[self.size + 1 - i]
    for istep = 1, step_count do
      local ofst = (istep - 1) * step_size * 2
      for j = 1, step_size do
        local a1, a2 = ret[ofst + j], ret[ofst + step_size + j]
        ret[ofst + j] = self:add(a1, self:mul(a2, wmul[1 + (j - 1) * step_count]))
        ret[ofst + step_size + j] = self:add(a1, self:mul(a2, wmul[1 + (j + step_size - 1) * step_count]))
      end
    end
  end
  return ret
end

TranFFT.fft = function(self, ary)
  return self:fft_common(ary, self.wmul)
end
TranFFT.ifft = function(self, ary)
  local ret = self:fft_common(ary, self.winvmul)
  for i = 1, self.n do
    ret[i] = self:mul(ret[i], self.ninv)
  end
  return ret
end

local k = io.read("*n")
-- math.randomseed(os.time())
-- local k = math.random(2, 100000)
-- print(k)
while k % 2 == 0 do
  k = mfl(k / 2)
end
while k % 5 == 0 do
  k = mfl(k / 5)
end
if k == 1 then print(1) os.exit() end

TranFFT:initialize()

local ret = {}
local inf = 1000000007
for i = 1, k do
  ret[i] = inf
end
local t = {}
for i = 1, TranFFT.n do
  t[i] = 0
end
t[1 + 1] = 1
ret[1] = 1
do
  local cur = 1
  while (cur * 10) % k ~= 1 do
    cur = (cur * 10) % k
    t[cur + 1] = 1
    ret[cur] = 1
  end
end

t = TranFFT:fft(t)
local tmp = {}
for i = 1, TranFFT.n do tmp[i] = t[i] end
local magic = 9
for iz = 2, magic do
  for i = 1, TranFFT.n do
    tmp[i] = TranFFT:mul(tmp[i], t[i])
  end
  tmp = TranFFT:ifft(tmp)
  if 0 < tmp[1] + tmp[1 + k] then
    print(iz) os.exit()
  end
  for i = 2, k do
    local v1, v2 = tmp[i], tmp[i + k]
    if v1 + v2 ~= 0 then
      tmp[i] = 1
      ret[i - 1] = mmi(ret[i - 1], iz)
    end
    tmp[i + k] = 0
  end
  tmp = TranFFT:fft(tmp)
  -- print(os.clock())
end


local tasks = {}
local edge = {}
for i = 1, k - 1 do
  if ret[i] == magic then
    table.insert(tasks, i)
  elseif ret[i] == 1 then
    table.insert(edge, i)
  end
end
local done = 0
while true do
  done = done + 1
  local src = tasks[done]
  local l = ret[src]
  for i = 1, #edge do
    local dst = (src + edge[i]) % k
    if dst == 0 then
      print(l + 1) os.exit()
    end
    if ret[dst] == inf then
      ret[dst] = l + 1
      table.insert(tasks, dst)
    end
  end
end


Measured memory_bytes: 50196