A - 通勤 Editorial /

Time Limit: 2.525 sec / Memory Limit: 246 MB

問題文

ニワンゴくんはdwango社のオフィスに通勤しています。家からオフィスまでの距離はNメートルです。 ニワンゴくんは人間ではないので、通勤の方法も少し特殊です。

具体的には、以下の2つの手順を行いオフィスに向かいます:

  • オフィスに向かってLメートル飛行する
  • Lの値をx倍にする。ただし、xはニコ数でなければならない。

この 2 つの手順は、好きな順番で、好きな回数だけ行うことができます。 ここで、ニコ数とは、10進法で表すとそれぞれの桁が2または5からなる正整数で、隣り合う桁の数字が異なるような数のことです。例えば、2525, 5, 525はニコ数ですが、225, 334, 5255 はニコ数ではありません。

また、Lの値ははじめは1です。

ニワンゴくんは、通勤時間を減らすため、オフィスに向かって合計でちょうどNメートル進むために必要な飛行回数の最小値を求めたいと思っています。 あなたの仕事は、ニワンゴくんに代わってこの最小値を求めるプログラムを書くことです。

入力

入力は以下の形式で標準入力から与えられる。

N
  • 1 行目には、オフィスまでの距離を表す整数 N(1 ≦ N ≦ 10^{18}) が与えられる。

部分点

この問題には部分点が設定されている。

  • N ≦ 10^5 を満たすデータセットに正解した場合、部分点として 30 点が与えられる。
  • 追加の制約のないデータセットに正解した場合、部分点として追加で 50 点が与えられる。合計で80点となる。

出力

ニワンゴくんの飛行回数の最小値を 1 行に出力せよ。 出力の最後には改行を忘れないこと。

入力例1

3

出力例1

2

以下の方法で、飛行回数2回で3メートル進むことができます。1回以下で3メートル進む方法はありません。

  • 1メートル飛行する
  • Lを2倍にする
  • 2メートル飛行する

入力例2

5

出力例2

1

入力例3

300

出力例3

2

入力例4

31

出力例4

3