[LSOT-1] 暴龙的土豆

暴龙爱吃土豆。

给定一个正整数 $n$。 每次操作可以选两个素数 $y,z$，其中要求 $z$ 是奇素数。 令 $x=y^z$，如果 $x$ 能除尽 $n$ 则计为一次有效操作，$n$ 变为 $\dfrac nx$。 现在需要你回答，对于 $n$ 最多能够进行多少次有效操作。

**本题有多组数据。** 第一行一个正整数 $T$。 接下来 $T$ 行，每行一个正整数 $n$。

对于每组数据，输出答案。

2
16
9

1
0

2
1327104
3623878656000

5
12

【样例解释】 对于样例一：$16$ 可以变成 $2^3 \times 2$，可以进行一次操作。但是 $9$ 只能变成 $3^2$，所以不能进行操作。 【数据范围】 **「本题采用捆绑测试」** - $\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)：}$无特殊限制。 对于 $100\%$ 的数据，满足 $1\le n\le 10^{18}$，$1\le T\le 10^2$。