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<=1e18）.

输出格式

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