Question
Swap Puzzle
Lila is given a positive integer M. In one move, she can either double M or divide it by 6 (if M is divisible by 6). Determine the minimum number of moves to reduce M to 1, or output -1 if impossible.
Input
First and the only line of input contains an integer M.
Constraints
1 ≤ M ≤ 109
Constraints
1 ≤ M ≤ 109
Output
Print the minimum number of moves to convert M to 1. Print -1, if it is not possible.
Example
Sample Input
18
Sample Output
3
Explanation
In the first move, we multiply 18 by 2, M = 36.
Now we divide it by 6, M = 6.
We again divide it by 6, M = 1.
18
Sample Output
3
Explanation
In the first move, we multiply 18 by 2, M = 36.
Now we divide it by 6, M = 6.
We again divide it by 6, M = 1.