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) of integers $$$x$$$ and $$$y$$$.

Input

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.

Output

For each test case, output a single number — the minimum number of layers.

Note

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.

Storming Arasaka

Examples