Balu, a lazy brown bear who teaches wolves the Law of the Jungle. He can wander where he pleases, because he eats only nuts, honey and roots.

This happened at the time when Baloo the bear taught Mowgli the Law of the Jungle. A large and important brown bear rejoiced at the abilities of a student, because wolf cubs usually learn from the Law of the Jungle only what their Pack and tribe need. But Mowgli, like a baby cub, needed to know much more.

In class on arithmetic, Baloo came up with the next game. It was necessary to get the number n from the number 1, while allowing the current number to be either multiplied by 3, or 4 to be added to the current number. For each multiplication, Baloo gave 5 cuffs, and for each addition 2 cuffs. For example,

In the first case one gets 10 cuffs, in the second case one gets 12 cuffs.

Mowgli naturally mastered arithmetic the best of all and quickly figured out how to solve a problem, having received the least number of cuffs. He also noticed that it is not always possible to complete the task of a cunning bear ...

Input

One integer n (1 ≤ n ≤ 109).

Output

Print the minimum number of cuffs that can be obtained for solving the problem. If the problem cannot be solved, then output number 0.