← 返回题目列表

Codeforces · 2238/D

D. 猛攻荒坂

中文机器翻译题面 查看原题

哈,你刚刚发现了如何成为传奇。
— 赛博朋克 2077

你和约翰尼·银手决定一起袭击荒坂。通过守卫后,你到达了神轿——但为了连接到它,你需要破解主服务器。

服务器密码的构成如下。有一个秘密号码$$$n$$$。考虑除 $$$1$$$ 之外的所有正因数, 但除数等于 $$$\mathbf{n}$$$ 被认为,和分区 全部 将它们分成几个非空层 $$$L_1, L_2, \ldots, L_k$$$。如果满足两个条件,则称分区良好:

  • 对于 $$$L_i$$$ 层中的任何除数 $$$x$$$,其所有除数($$$1$$$ 和 $$$x$$$ 除外)仅位于 $$$L_1, L_2, \ldots, L_{i-1}$$$ 层中;
  • 在每一层中,所有数字都可以排序成一条链,使得该链中任意两个相邻数字的GCD$$$^{\text{*}}$$$大于$$$1$$$。

密码的长度定义为层数$$$k$$$。为了层的安全性,层的数量必须尽可能小。

幸运的是,自从约翰尼时代以来,荒坂就没有改变过$$$n$$$,并且他记得这个数字的几个可能的值。对于每个层,帮助 V 和 Johnny 确定可能的最小层数。

$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) - Johnny 告诉你的秘密数字的候选值。

输出

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

示例

输入
复制

8
2
4
8
16
32
67
120
33

输出
复制

1
2
3
4
5
1
7
3

注意

在第一个 $$$5$$$ 测试用例中,给定数字的形式为 $$$2^k$$$。让我们证明他们的答案是$$$k$$$。考虑除 $$$1$$$ 之外的所有正因数:$$$2^1, 2^2, \ldots, 2^{k}$$$。很明显,它们中的任何两个都不能位于同一层,这意味着它们全部位于不同的层中。排列的一个例子是:$$$L_i = \{2^i\}$$$。显然,它满足条件,并且恰好获得了$$$k$$$层。