Problem Description

Niwango-kun commutes to the office of dwango. The distance from his home to the office is $N$ meters. Since Niwango-kun is not human, his method of commuting is a bit special.

Specifically, he follows these two steps to head towards the office:

• Fly $L$ meters towards the office.
• Multiply the value of $L$ by $x$, where $x$ must be a Nico number.

These two steps can be performed in any order and any number of times. Here, a Nico number is a positive integer where each digit in its decimal representation is either 2 or 5, and adjacent digits are different. For example, $2525$, $5$, and $525$ are Nico numbers, but $225$, $334$, and $5255$ are not.

Additionally, the initial value of $L$ is 1.

Niwango-kun wants to reduce his commuting time and is looking for the minimum number of flights needed to travel exactly $N$ meters towards the office. Your task is to write a program that calculates this minimum value on behalf of Niwango-kun.

Input Format

The input is given from the standard input in the following format:

$N$

• The first line contains an integer $N$ representing the distance to the office, where $1 \leq N \leq 10^{18}$.

Output Format

Output the minimum number of flights Niwango-kun needs to travel exactly $N$ meters in one line. Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

3

Sample Output #1

2

Sample Input #2

5

Sample Output #2

1

Sample Input #3

300

Sample Output #3

2

Sample Input #4

31

Sample Output #4

3

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $N \leq 10^5$, you will be awarded 30 points.
• If you solve the dataset without additional constraints, you will be awarded an additional 50 points, totaling 80 points.

Sample Explanation 1

The following method allows traveling 3 meters with 2 flights. There is no way to travel 3 meters with 1 flight or less.
- Fly 1 meter.
- Multiply $L$ by 2.
- Fly 2 meters.

见题面 Input 部分

见题面 Output 部分