問題文

ニワンゴくんは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

---