{"raw_statement":[{"iden":"background","content":"在 QQ 群中，经常会出现这样的接龙：\n- 万人血书 xxx（1/10000）$\\to$\n- 万人血书 xxx（1/5000）$\\to$\n- 万人血书 xxx（1/2500）$\\to$\n- 万人血书 xxx（1/1250）$\\to \\dots$\n\n以此类推，在可以约分的情况下，“万人血书”很快就能完成。"},{"iden":"statement","content":"“$x$ 人血书”的过程可以看成一个函数 $f(x)$：\n\n有一个 $\\frac{0}{x}$ 的分数。重复以下步骤直到这个分数为 $1$：\n\n1. 分子 $+1$。\n2. 如果这个分数可以约分，约分到最简形式。\n\n现在小 D 给了你 $T$ 组数据，每组数据都是给定 $n$，求在 $1\\le x\\le n$ 的情况下 $f(x)$ 的最大操作次数。\n\n但是他太菜了，不会，你能帮帮他吗？"},{"iden":"input","content":"第一行一个正整数 $T$。\n\n接下来 $T$ 行，每行一个正整数 $n$。"},{"iden":"output","content":"共 $T$ 行，每行一个整数 $s$ 表示在 $1\\le x\\le n$ 的情况下 $f(x)$ 的最大操作次数。"},{"iden":"note","content":"### 样例解释\n\n$f(1)=1,f(2)=2,f(3)=3,f(4)=3,f(5)=5$。\n\n我也想把更大的 $f(x)$ 列出来，但是地方不够了。\n\n### 数据范围\n\n\n对于全部数据，$1\\le T\\le 5\\times 10^5$，$1\\le n\\le 2\\times 10^6$。\n\nSubtask 中没填的部分表示和全部数据的范围一样。\n\n| 子任务编号 | $T$ 的范围 | $n$ 的范围 | 特殊性质 |分值|\n| -----------: | -----------: | -----------: | -----------: |-----------: |\n| Subtask $1$ | $T\\le 3$ | $n\\le 10$ |  |$10$|\n| Subtask $2$ | $T\\le 5$ | $n\\le 10^3$ |  |$30$|\n| Subtask $3$ |  |  | $n$ 为质数|$10$|\n| Subtask $4$  |  | $n\\le 5\\times 10^5$ |  |$20$|\n| Subtask $5$  |  |  |  |$30$|\n"}],"translated_statement":null,"sample_group":[["5\n1\n2\n5\n8\n114514","1\n2\n5\n7\n114493\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}