Từ một số nguyên dương ~K~, thực hiện biến đổi số ~K~ theo quy tắc biến đổi sau đây:

• Nếu ~K~ chia hết cho ~6~ thì thay số ~K~ bởi thương ~K~ chia cho ~6~.
• Nếu ~K~ không chia hết cho ~6~ thì thay số ~K~ bởi tích ~3×K~.

Hãy xác định số lần biến đổi theo quy tắc trên để ~K~ bằng ~1~.

Input

• Một dòng chứa số nguyên ~K~ (~1 ≤ K ≤ 10^{12})~ .

  Output

• In ra số nguyên dương ~m~ là số lần biến đổi để số ~K~ bằng ~1~. Trong trường hợp không thể biến đổi được thì in ra ~-1~.

Sample Input 1

12

Sample Output 1

3

Note

~12 ÷ 6 = 2~

~2×3 = 6~

~6 ÷ 6 = 1~

Sample Input 2

10

Sample Output 2

-1