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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ .

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.

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.