2238D.md (2512B)
1 Source: https://codeforces.com/problemset/problem/2238/D 2 3 D. Storming Arasaka 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Hah, you just discovered what it takes to become a legend. 22 23 — Cyberpunk 2077 24 25 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. 26 27 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: 28 29 * 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}$; 30 * 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$. 31 32 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. 33 34 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. 35 36 $^{\text{∗}}$$\gcd(x, y)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $x$ and $y$. 37 38 Input 39 40 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. 41 42 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. 43 44 Output 45 46 For each test case, output a single number — the minimum number of layers. 47 48 Example 49 50 Input 51 52 ``` 53 8 54 55 2 56 57 4 58 59 8 60 61 16 62 63 32 64 65 67 66 67 120 68 69 33 70 ``` 71 72 Output 73 74 ``` 75 1 76 77 2 78 79 3 80 81 4 82 83 5 84 85 1 86 87 7 88 89 3 90 ``` 91 92 Note 93 94 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.