喵~ 主人，下午好呀！今天由本喵来为主人讲解一道非常有趣的数学问题。只要稍微动动脑筋，分析一下数字变化的本质，就能像魔法一样轻松解决它哦！一起来看看吧，喵~

Problem: 1374B - Multiply by 2, divide by 6

---

题目大意

主人会给喵一个整数 n。喵有两种魔法可以用哦：

1. 把 n 乘以 2。
2. 如果 n 能被 6 整除（也就是没有余数），就把 n 除以 6。

喵的目标是，用 最少 的魔法次数，把 n 变成 1。如果无论如何都变不成 1，就要告诉主人这是不可能的，并输出 -1。我们需要处理好多好多组这样的询问呢，喵。

---

解题思路

这道题看起来像是要我们一步步尝试，但那样太慢啦，喵~ 让我们来分析一下这两个魔法的本质吧！

• 乘以 2：这相当于给数字 n 的质因数分解式里增加一个因子 2。
• 除以 6：因为 6 = 2 * 3，所以这相当于从 n 的质因数分解式里拿走一个因子 2 和一个因子 3。

你看，所有的操作都只和质因数 2 和 3 有关。如果最开始的数字 n 含有除了 2 和 3 以外的质因数（比如 5, 7, 11...），那我们无论用哪种魔法，都永远消不掉它们，也就永远不可能把 n 变成 1 了。

所以，我们的第一步就是检查 n 是不是只由因子 2 和 3 构成。一个简单的办法是：把 n 里面所有的 2 和 3 都除掉，看看最后是不是剩下 1。如果不是 1，那就直接判定为不可能，输出 -1，喵~

好，现在我们确定了 n 的形式一定是 2^a * 3^b（这里 a 是质因数 2 的个数，b 是质因数 3 的个数）。我们的目标是把它变成 1，也就是 2^0 * 3^0。

让我们来分析一下如何改变 a 和 b 这两个幂次：

• * 2 操作：(a, b) -> (a+1, b)
• / 6 操作：(a, b) -> (a-1, b-1)

怎么处理因数 3 呢？ 想把 3^b 变成 3^0，唯一的办法就是用 / 6 这个魔法，因为 * 2 不会影响 3 的个数。每用一次 / 6，3 的幂次就减 1。所以，我们 必须 恰好使用 b 次 / 6 的魔法。

使用 b 次 / 6 魔法后会发生什么？ 3 的幂次成功变成了 0，太棒了！但是，2 的幂次也受到了影响。原来是 a，现在用掉了 b 次 / 6，所以 2 的幂次变成了 a - b。 所以，我们现在的数字是 2^(a-b) * 3^0。

怎么处理剩下的因数 2 呢？ 我们现在的目标是把 2^(a-b) 变成 2^0。我们手里还有 * 2 这个魔法。* 2 会让 2 的幂次加 1。 所以，我们需要进行 k 次 * 2 操作，使得 (a - b) + k = 0。 解出来就是 k = b - a。

最后的条件！ 操作次数 k 必须是大于等于 0 的呀，我们不能乘 -2 次 2 吧，喵~ 所以，b - a >= 0，也就是 b >= a。换句话说，n 中质因数 3 的数量必须大于或等于质因数 2 的数量。如果 a > b，那就不可能变到 1 了。因为除以 6 会把 2 消耗得比 3 还快，最后就算 3 没了，2 还会有剩，而且我们没法再减少 2 的幂次了（/ 6 需要有 3 呀）。

总结一下喵的思路：

1. 先把 n 中所有的 2 和 3 都除干净。
2. 如果剩下的 n 不是 1，说明有其他质因数，不可能，输出 -1。
3. 统计 n 中质因数 2 的个数（记为 count2）和 3 的个数（记为 count3）。
4. 如果 count2 > count3，不可能，输出 -1。
5. 如果可以，那么总操作次数 = (/ 6 的次数) + (* 2 的次数) = count3 + (count3 - count2) = 2 * count3 - count2。

是不是很简单喵？~

---

题解代码

这是喵为主人准备的 C++ 代码，加上了可爱的注释哦！

#include <iostream>

void solve() {
    int n;
    std::cin >> n;

    // 如果一开始就是1，那就不需要动啦，0步~
    if (n == 1) {
        std::cout << 0 << "\n";
        return;
    }

    // 喵来数一数有多少个因数2
    int count2 = 0;
    while (n % 2 == 0) {
        n /= 2;
        count2++;
    }

    // 喵再来数一数有多少个因数3
    int count3 = 0;
    while (n % 3 == 0) {
        n /= 3;
        count3++;
    }

    // 如果把2和3都除完，剩下的不是1，说明有别的捣蛋鬼因数，变不成1的！
    // 并且，因数3的个数必须大于等于因数2的个数才行哦 (count2 <= count3)
    if (n == 1 && count2 <= count3) {
        // 总步数 = 除以6的次数 + 乘以2的次数
        // 除以6的次数必须是 count3 次，为了消掉所有的3
        // 乘以2的次数就是 count3 - count2 次，为了补上除以6时多消耗的2
        // 总共就是 count3 + (count3 - count2) = 2 * count3 - count2
        std::cout << 2 * count3 - count2 << "\n";
    } else {
        // 不满足条件，就是不可能啦
        std::cout << -1 << "\n";
    }
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

知识点介绍

这道题用到了哪些小知识呢？喵来总结一下！

• 质因数分解 (Prime Factorization) 每个大于1的整数都可以被分解成一串质数的乘积，而且这种分解方式是唯一的哦！比如 12 = 2 * 2 * 3 = 2^2 * 3^1。这道题的核心就是把对数字 n 的操作，转换成对它质因数幂次的操作。这样一来，问题就从复杂的乘除法，变成了简单的加减法，是不是清晰多啦？喵~

• 构造性思维 (Constructive Thinking) 我们没有去漫无目的地搜索，而是分析了目标（变成1）和手段（两种操作）的特性。我们发现，为了消除因数3，必须执行特定次数的 / 6 操作。这个发现是解题的关键，它帮我们“构造”出了一条通往答案的唯一路径，然后我们只需要检查这条路能不能走通就行了。这种从目标反推过程的思维方式，在解决很多问题时都非常有用哦，主人要记住喵！

希望本喵的讲解对主人有帮助！如果还有其他问题，随时可以再来找我哦~ 喵~