Baloo, a lazy brown bear, teaches wolf cubs the Law of the Jungle. He is free to wander wherever he pleases, because he eats only nuts, honey, and roots.
This story takes place when the bear Baloo was teaching Mowgli the Law of the Jungle. The large and respected brown bear was proud of his pupil's abilities, as wolf cubs typically learn only what their Pack and tribe require from the Law. But Mowgli, being a human child, needed to know much more.
During arithmetic lessons, Baloo invented the following game. One must obtain the number starting from . At each step, you may either multiply the current number by , or add to the current number. For each multiplication, Baloo gives cuffs, and for each addition, cuffs. For example,

in the first case you get 10 cuffs, and in the second case you get 12 cuffs.
Naturally, Mowgli learned arithmetic best of all and quickly figured out how to solve the problem, obtaining the least number of cuffs. He also noticed that it is not always possible to complete the task set by the cunning bear...
One integer (1 \le n \le 10^9).
Print the minimum number of cuffs required to solve the problem. If the problem cannot be solved, print the number 0.
Example 1
Example 2