你和约翰尼·银手决定一起袭击荒坂。通过守卫后,你到达了神轿——但为了连接到它,你需要破解主服务器。
服务器密码的构成如下。有一个秘密号码$$$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 告诉你的秘密数字的候选值。
输出
对于每个测试用例,输出一个数字 - 最小层数。
示例
输入复制
824816326712033
输出复制
12345173
注意
在第一个 $$$5$$$ 测试用例中,给定数字的形式为 $$$2^k$$$。让我们证明他们的答案是$$$k$$$。考虑除 $$$1$$$ 之外的所有正因数:$$$2^1, 2^2, \ldots, 2^{k}$$$。很明显,它们中的任何两个都不能位于同一层,这意味着它们全部位于不同的层中。排列的一个例子是:$$$L_i = \{2^i\}$$$。显然,它满足条件,并且恰好获得了$$$k$$$层。