CF2238D Storming Arasaka

哈哈，你刚刚发现了成为传奇所需的一切。 ——《赛博朋克 2077》 你和 Johnny Silverhand 决定一起向荒坂公司发起冲锋。你们在击败守卫后来到了 Mikoshi，但要连接到 Mikoshi，你需要黑进主服务器。 服务器的密码是这样组成的。有一个秘密数字 $n$。考虑它的所有正因数（不包括 $1$，但包括因子 $n$ 本身），将它们划分为若干个非空的层 $L_1, L_2, \ldots, L_k$。当且仅当满足以下两个条件时，这个划分被称为“好的”： - 对于层 $L_i$ 中的任意一个因数 $x$，$x$ 的所有因数（不包括 $1$ 和 $x$ 本身）都只出现在层 $L_1, L_2, \ldots, L_{i-1}$ 中； - 在每一层中，所有的数字都可以排列成一条链，使得链中任意相邻的两个数的最大公约数大于 $1$。 密码的长度定义为层数 $k$。为保证层的安全，层数应尽可能小。 幸运的是，荒坂公司自 Johnny 的时代以来没有更改过 $n$，而他还记得这个数字的几个可能的取值。对于每一个数字，请你帮助 V 和 Johnny 计算出最小可能的层数。 注：$\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 接下来每个测试用例一行，包含一个整数 $n$（$2 \le n \le 10^6$），为 Johnny 提到的秘密数的一个候选值。

对于每个测试用例，输出一行一个整数，表示最小的层数。

对于前 $5$ 个测试用例，给定的数字形式为 $2^k$。我们证明这时的答案就是 $k$。考虑所有正因数（不包括 $1$）：$2^1, 2^2, \ldots, 2^{k}$。显然它们不能放在同一层，因此必定各自单独分层。例如：$L_i = \{2^i\}$。可以看出它满足条件，且恰好有 $k$ 层。 由 ChatGPT 5 翻译