# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20358
#
# 巡回数 => ダイヤル数(Wikipedia)
#
# ダイヤル数 n は，1 / mの循環節に現れる．
# 循環節がダイヤル数となる m を母ダイヤル数と呼ぶことにする．
# m が母ダイヤル数となる条件は，
#  1. m は素数である．
#  2. 10 ** k - 1 が m の倍数となる k が m - 1のみである．
# また m が n の母ダイヤル数であるとき,
#  (10 ** (m - 1) - 1) / m = n である．
#
# 参考: http://kigurom.web.fc2.com/HP2/report/018/018.html
#
# 問題より n の下位5桁は 56789 である．
# 
# (10 ** (m - 1) -1) = m * n
# なので
#  (10 ** (m - 1) -1) % (10 ** 5) = (m * 56789) % (10 ** 5)
# より m の下位5桁が求められる．(mlowとする）
#
# n の先頭が 00000000137 より m は 100000000 以上なので，
# i = 1000 を初期として
#  m = i * 10 ** 5 + mlow
# で i を増やしながら m の候補を生成する．
# m が素数かつ
#  (10 ** (m - 1) ) % m = 1
# かつ
#  (1 / m * 10 ** 11).floor = 137
# かつ循環節の長さが m - 1 なら
# 循環節の各桁の合計が答えになる．
# 
require 'prime'
mlow = -1

# m の下位5桁を求める．
Prime.each do |m|
  if (m * 56789 % (10 ** 5) == 99999)
    # m の下位5桁
    mlow = m % (10 ** 5)
    break
  end
end

# (10 ** (m - 1)) % mを計算するためにmodpowを使う．
def modpow(b, e, m)
  c = 1
  while e > 0
    if (e & 1) == 1
      c = c * b % m
    end
    e = e >> 1
    b = b * b % m
  end
  c
end

# 1 / m の循環節の長さと各桁の合計を求める．
def repetend(n)
  len = 0
  sum = 0
  m = 1 % n
  begin
    len += 1
    d, m = (m * 10).divmod(n)
    sum += d
  end while (m != 1)
  [len, sum]
end

# m を探索．
i = 1000
loop do
  m = i * 10 ** 5 + mlow
  if ((1.0 / m * (10 ** 11)).floor == 137 &&
      m.prime? &&
      modpow(10, m - 1, m) == 1)
    len, sum = repetend(m)
    if (len == m - 1)
      puts sum
      break
    end
  end
  i += 1
end