Background

The Tyrannosaurus loves eating potatoes.

Problem Description

Given a positive integer $n$.

In each operation, you may choose two primes $y, z$, where $z$ must be an odd prime.

Let $x = y^z$. If $x$ divides $n$, then it counts as one valid operation, and $n$ becomes $\dfrac{n}{x}$.

Now you need to answer: for a given $n$, what is the maximum number of valid operations that can be performed.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$.

The next $T$ lines each contain a positive integer $n$.

Output Format

For each test case, output the answer.

2
16
9

1
0

2
1327104
3623878656000

5
12

Hint

[Sample Explanation]

For sample 1: $16$ can be written as $2^3 \times 2$, so one operation can be performed. But $9$ can only be written as $3^2$, so no operation can be performed.

[Constraints]

"This problem uses bundled testdata."

• $\texttt{Subtask 1(10 pts)：}1 \le\ n\le 10^2，1 \le\ T\le 10^2$；
• $\texttt{Subtask 2(20 pts)：}1 \le\ n\le 10^6，1 \le\ T\le 10^2$；
• $\texttt{Subtask 3(30 pts)：}1 \le\ n\le 10^{12}，1 \le\ T\le 10^2$；
• $\texttt{Subtask 4(40 pts)：}$No special constraints.

For $100\%$ of the testdata, $1 \le n \le 10^{18}$ and $1 \le T \le 10^2$.

Translated by ChatGPT 5