P8448 [LSOT-1] Tyrannosaurus’s Potatoes

The Tyrannosaurus loves eating potatoes.

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.

**This problem contains multiple test cases.** The first line contains a positive integer $T$. The next $T$ lines each contain a positive integer $n$.

For each test case, output the answer.

[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