问题描述

尼瓦古君每天通勤到dwango公司的办公室。从家到办公室的距离是$N$米。由于尼瓦古君不是人类，所以他的通勤方式有些特殊。

具体来说，他按照以下两个步骤前往办公室：

• 飞行$L$米前往办公室
• 将$L$乘以$x$。其中，$x$必须是一个“尼科数”。

这两个步骤可以按任意顺序，重复任意次数。这里，“尼科数”是一个十进制表示的正整数，每个位都是2或5，并且相邻位的数字不相同。例如，2525、5和525都是尼科数，但225、334和5255不是。

初始时，$L$的值为1。

尼瓦古君想知道为了减少通勤时间，他需要进行多少次飞行才能总共前进恰好$N$米。你的任务是代替尼瓦古君编写一个程序来计算这个最小值。

---

输入

输入以以下格式从标准输入中给出。

$N$

• 第1行包含一个整数$N(1 \leq N \leq 10^{18})$，表示到办公室的距离。

子任务

本问题共有两个子任务。

• 当$N \leq 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