Problem Description

You have a wonderful car that has an automatic acceleration feature. For example, on the first day, you can drive it for a distance of \(a\). On the second day, you can increase the distance to 2 to 9 times the first day's distance (must be an integer), which means \(2a\) to \(9a\). On the third day, the distance driven will be 2 to 9 times the second day's distance, and so on. In other words, the distance driven on the \(i\)-th day must be an integer multiple of 2 to 9 times the distance driven on the \((i-1)\)-th day.

Now, you are eager to drive this car from City A to City B for a trip, showcasing this extraordinary car along the way. You know the total distance \(S\) you need to travel. Please arrange the distance for the first day and the multiplier for each subsequent day so that you can reach City B exactly in the shortest number of days.

However, since you want to fully demonstrate your car and also for safety reasons, you are required to spend at least 2 days. If no such plan can be found, please output -1.

Input Format

A positive integer \(S\), representing the distance from City A to City B.

Output Format

A number representing the minimum number of days required to travel, or -1 if there is no solution.

Sample Input and Output

Sample Input #1

15121

Sample Output #1

-1

Sample Input #2

571

Sample Output #2

5

Notes

Data Scale

• For 30% of the data, \(S \leq 100\);
• For 70% of the data, \(S \leq 10^7\);
• For 100% of the data, \(9 < S \leq 10^8\).

见题面 Input 部分

见题面 Output 部分