该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个整数 $n$。在一次操作中，您可以将 $n$ 乘以 $2$，或者将 $n$ 除以 $6$（如果它能被 $6$ 整除且没有余数）。

您的任务是找出从 $n$ 获得 $1$ 所需的最小操作次数，或者确定是否不可能做到这一点。

输入格式

仅一行，包含一个整数 $n$ ($1 \le n \le 10^9$)。

输出格式

如果可能从 $n$ 获得 $1$，请输出所需的最小操作次数。

如果不可能从 $n$ 获得 $1$，请输出 $-1$。

输入输出样例

1

0

2

-1

3

2

12

-1

12345

-1

15116544

12

387420489

36

解释

考虑第六个测试用例，答案可以通过以下操作序列从给定整数 $15116544$ 获得：

除以 6 得到 2519424;
除以 6 得到 419904;
除以 6 得到 69984;
除以 6 得到 11664;
乘以 2 得到 23328;
除以 6 得到 3888;
除以 6 得到 648;
除以 6 得到 108;
乘以 2 得到 216;
除以 6 得到 36;
除以 6 得到 6;
除以 6 得到 1.