{"raw_statement":[{"iden":"background","content":"暴龙爱吃土豆。"},{"iden":"statement","content":"给定一个正整数 $n$。\n\n每次操作可以选两个素数 $y,z$，其中要求 $z$ 是奇素数。\n\n令 $x=y^z$，如果 $x$ 能除尽 $n$ 则计为一次有效操作，$n$ 变为 $\\dfrac nx$。\n\n现在需要你回答，对于 $n$ 最多能够进行多少次有效操作。"},{"iden":"input","content":"**本题有多组数据。**\n\n第一行一个正整数 $T$。\n\n接下来 $T$ 行，每行一个正整数 $n$。"},{"iden":"output","content":"对于每组数据，输出答案。"},{"iden":"note","content":"【样例解释】\n\n对于样例一：$16$ 可以变成 $2^3 \\times 2$，可以进行一次操作。但是 $9$ 只能变成 $3^2$，所以不能进行操作。\n\n【数据范围】\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(10 pts)：}1 \\le\\ n\\le 10^2，1 \\le\\ T\\le 10^2$；\n- $\\texttt{Subtask 2(20 pts)：}1 \\le\\ n\\le 10^6，1 \\le\\ T\\le 10^2$；\n- $\\texttt{Subtask 3(30 pts)：}1 \\le\\ n\\le 10^{12}，1 \\le\\ T\\le 10^2$；\n- $\\texttt{Subtask 4(40 pts)：}$无特殊限制。\n\n对于 $100\\%$ 的数据，满足 $1\\le n\\le 10^{18}$，$1\\le T\\le 10^2$。"}],"translated_statement":null,"sample_group":[["2\n16\n9","1\n0"],["2\n1327104\n3623878656000","5\n12"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}