Description

You have a wonderful car with an auto-acceleration feature. For example, on day $1$ you can drive a distance of $a$. Then on day $2$, you can increase the distance to one of $2$ to $9$ times that of day $1$ (it must be one of these integers), that is, from $2a$ to $9a$. On day $3$, the distance will be $2$ to $9$ times that of day $2$, and so on. In other words, on day $i$, the distance must be $2$ to $9$ times that of day $i-1$, and it must be an integer multiple of it.

You are eager to drive this car from city $A$ to city $B$ for a trip and show off this extraordinary car along the way. You already know the total mileage $S$ you need to travel. Please determine the day $1$ distance and the multiplier used each subsequent day so that the total distance is exactly $S$ and the number of days is minimized.

However, because you want to show off your car properly and for safety reasons, you are required to spend at least $2$ days. If no such plan exists, output -1.

Input Format

A positive integer $S$, representing the distance from city $A$ to city $B$.

Output Format

A single integer representing the minimum number of days required; if there is no solution, output -1.

15121

-1

571

5

Hint

Constraints

• For $30\%$ of the testdata, $S \leq 100$.
• For $70\%$ of the testdata, $S \leq 10^7$.
• For $100\%$ of the testdata, $9 < S \leq 10^8$.

Translated by ChatGPT 5