AT_dwango2016final_a 通勤

nwango君去dwango公司的办公室上班。从家到办公室的距离是N米。因为nwango君不是人类，所以通勤的方法也有点特殊。具体来说，我们有两个步骤: 1：向办公室飞L米。 2：使L的值为变为x倍。不过，x必须是尼可数字。 这两个步骤，你可以按照你喜欢的顺序，执行你喜欢的次数。 这里，尼可数字是指10进制中各位数为2或5位数的正整数，且相邻位数的数字彼此不同。例如，2525、 5、 525 、2525、525是尼可数字，但是225、334、 5255、334和5255不是尼可数字。同时，L的值开始是1。 为了减少上下班时间，他想要寻求向办公室总共前进N米所需的飞行次数的最小值。（nwango君只会飞固定路程，即使飞过了办公室也不会停下）你的工作是写代替niwango君计算这个最小值的程序。

通过标准输入模式来提供以下模式的输入。 第一行：表示到办公室的距离N（1

第一行：飞行最少次数（末尾需要换行）。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 10^5 $ を満たすデータセットに正解した場合、部分点として $ 30 $ 点が与えられる。 - 追加の制約のないデータセットに正解した場合、部分点として追加で $ 50 $ 点が与えられる。合計で$ 80 $点となる。 ### Sample Explanation 1 以下の方法で、飛行回数$ 2 $回で$ 3 $メートル進むことができます。$ 1 $回以下で$ 3 $メートル進む方法はありません。 - $ 1 $メートル飛行する - $ L $を$ 2 $倍にする - $ 2 $メートル飛行する