{"problem":{"name":"[LSOT-1] 暴龙的土豆","description":{"content":"给定一个正整数 $n$。 每次操作可以选两个素数 $y,z$，其中要求 $z$ 是奇素数。 令 $x=y^z$，如果 $x$ 能除尽 $n$ 则计为一次有效操作，$n$ 变为 $\\dfrac nx$。 现在需要你回答，对于 $n$ 最多能够进行多少次有效操作。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8448"},"statements":[{"statement_type":"Markdown","content":"给定一个正整数 $n$。\n\n每次操作可以选两个素数 $y,z$，其中要求 $z$ 是奇素数。\n\n令 $x=y^z$，如果 $x$ 能除尽 $n$ 则计为一次有效操作，$n$ 变为 $\\dfrac nx$。\n\n现在需要你回答，对于 $n$ 最多能够进行多少次有效操作。\n\n## Input\n\n**本题有多组数据。**\n\n第一行一个正整数 $T$。\n\n接下来 $T$ 行，每行一个正整数 $n$。\n\n## Output\n\n对于每组数据，输出答案。\n\n[samples]\n\n## Background\n\n暴龙爱吃土豆。\n\n## Note\n\n【样例解释】\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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8448","tags":["数学","洛谷原创"],"sample_group":[["2\n16\n9","1\n0"],["2\n1327104\n3623878656000","5\n12"]],"created_at":"2026-03-03 11:09:25"}}