Storming ArasakaAI (CI翻译)
Hah, you just discovered what it takes to become a legend.— Cyberpunk 2077
You and Johnny Silverhand decided to storm Arasaka together. After making your way through the guards, you reached Mikoshi — but in order to connect to it, you need to hack the main server.
The password to the server is formed as follows. There is a secret number $n$. Consider all of its positive divisors except $1$, but the divisor equal to ** $\mathbf{n}$ ** is considered, and partition all of them into several nonempty layers $L_1, L_2, \ldots, L_k$. A partition is called good if two conditions are satisfied:
- for any divisor
$x$from layer$L_i$, all of its divisors, except$1$and$x$, lie only in the layers$L_1, L_2, \ldots, L_{i-1}$; - in each layer, all numbers can be ordered into a chain so that any two neighboring numbers in this chain have GCD
$^{\text{∗}}$greater than$1$.
The length of the password is defined as the number of layers $k$. For the security of the layers, their number must be as small as possible.
Fortunately, Arasaka has not changed $n$ since Johnny's time, and he remembers several possible values of this number. For each of them, help V and Johnny determine the minimum possible number of layers.
$^{\text{∗}}$$\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The only line of each test case contains a single integer $n$ ($2 \le n \le 10^6$) — a candidate value of the secret number that Johnny told you.
Output
For each test case, output a single number — the minimum number of layers.
Note
In the first $5$ test cases, the given number has the form $2^k$. Let us show that the answer for them is $k$. Consider all positive divisors except $1$: $2^1, 2^2, \ldots, 2^{k}$. It is clear that no two of them can lie in the same layer, which means that all of them lie in different layers. An example of an arrangement is: $L_i = \{2^i\}$. It is clear that it satisfies the conditions, and exactly $k$ layers are obtained.
{"titleZh":"突袭荒坂","bodyZh":"Hah，你刚刚发现了成为传奇所需的一切。——《赛博朋克 2077》\n\n你和 Johnny Silverhand 决定一起突袭荒坂。在突破守卫后，你们到达了 Mikoshi——但为了连接到它，你需要入侵主服务器。\n\n服务器的密码按如下方式构成。存在一个秘密数字 $n$。考虑它的所有正因数（除了 $1$，但等于 ** $\mathbf{n}$ ** 的因数也要考虑），并将所有这些因数划分为若干个非空层 $L_1, L_2, \\ldots, L_k$。如果一个划分满足以下两个条件，则称其为好的划分：\n\n- 对于层 $L_i$ 中的任意因数 $x$，除了 $1$ 和 $x$ 之外，$x$ 的所有因数都只位于层 $L_1, L_2, \\ldots, L_{i-1}$ 中；\n- 在每一层中，所有数字都可以排列成一个链，使得链中任意两个相邻数字的 GCD$^{\\text{∗}}$ 都大于 $1$。\n\n密码的长度定义为层数 $k$。为了保证层的安全性，层数必须尽可能少。\n\n幸运的是，自 Johnny 的时代起，荒坂一直没有更改 $n$，而他记得这个数字的若干个可能取值。对于每个取值，请帮助 V 和 Johnny 求出可能的最小层数。\n\n$^{\\text{∗}}$$\\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数（GCD）。\n\n## 输入格式\n\n每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \\le t \\le 10^4$）。接下来是各测试用例的描述。\n\n每个测试用例仅包含一行，其中包含一个整数 $n$（$2 \\le n \\le 10^6$）——Johnny 告诉你的秘密数字的一个候选值。\n\n## 输出格式\n\n对于每个测试用例，输出一个数字——最小层数。\n\n## 说明\n\n在前 $5$ 个测试用例中，给定的数字形如 $2^k$。下面证明这些测试用例的答案为 $k$。考虑除了 $1$ 之外的所有正因数：$2^1, 2^2, \\ldots, 2^{k}$。显然，其中任意两个都不能位于同一层，这意味着它们必须分别位于不同的层中。一种可行的划分方式是：$L_i = \\{2^i\\}$。显然，它满足条件，并且恰好得到 $k$ 层。"}AI (CI翻译)
样例
8
2
4
8
16
32
67
120
33
1
2
3
4
5
1
7
3
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。