CF2238D.Storming Arasaka

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$.

哈哈，你刚刚发现了成为传奇所需要的一切。

——《赛博朋克2077》

你与强尼·银手决定联手突袭荒坂公司。在突破守卫之后，你们抵达了“御所”（Mikoshi）——但为了接入它，你们需要黑入主服务器。

服务器的密码构造方式如下：存在一个秘密数字 $n$。考虑 $n$ 的所有正因数（除 $1$ 外），但包含因数 $n$ 本身，并将这些因数划分为若干个非空层 $L_1, L_2, \ldots, L_k$。若一个划分满足以下两个条件，则称其为好划分：

• 对于任意层 $L_i$ 中的因数 $x$，$x$ 的所有因数（除 $1$ 和 $x$ 本身外）均仅出现在层 $L_1, L_2, \ldots, L_{i-1}$ 中；
• 在每一层中，所有数字均可排列成一条链，使得该链中任意两个相邻数字的 $\gcd^{\text{∗}}$ 均大于 $1$。

密码的长度定义为层数 $k$。为保障各层的安全性，层数必须尽可能小。

幸运的是，荒坂公司自强尼的时代以来一直未更改 $n$，而他仍记得该数字的若干可能取值。对其中每一个值，请帮助V和强尼确定最小可能的层数。

$^{\text{∗}}$$\gcd(x, y)$ 表示整数 $x$ 与 $y$ 的最大公约数（GCD）。

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.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$2 \le n \le 10^6$）—— Johnny 告诉你的秘密数字的一个候选值。

For each test case, output a single number — the minimum number of layers.

对于每个测试用例，输出一个数字——最小层数。

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.

在前 $5$ 个测试用例中，给定的数形如 $2^k$。我们来证明：这些测试用例的答案为 $k$。考虑除 $1$ 外的所有正因数：$2^1, 2^2, \ldots, 2^{k}$。显然，其中任意两个数都不能位于同一层，因此它们全部位于不同的层中。一种可行的分层方案是：$L_i = \{2^i\}$。显然该方案满足所有条件，且恰好得到 $k$ 层。