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). 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 dif