题目背景

暴龙爱吃土豆。

题目描述

给定一个正整数 $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$。