P1066月的第十二章（moon）

【题目背景】

《月》是一部写给长夜的旅行札记。作者曾将每一次月升后的见闻写成一章，前十一章都记下了启程与归来的故事，唯独第十二章只留下开头的一行，便随着旧稿一起沉寂了许多年。

如今，你在整理书稿时重新翻开了《月》。窗外的月色与旧日无异，残页上的文字却仍停在旅途开始的地方。你决定遵循作者留在页边的规则继续写下去，让这段迟来的旅程抵达终点，也让《月》拥有完整的第十二章。

【题目描述】

第十二章的扉页上写着这段旅程最终应当由 $y$ 行文字组成。旧稿中已经留下了第一行，它既是故事的开头，也是你续写时唯一能够依循的内容。用正整数 $x$ 表示当前已经写完的行数，则开始时 $x=1$。

续写不能任意进行。作者在页边写下了一条与篇幅有关的规则：每个夜晚，你可以选择一个满足 $1\leq k\leq \gcd(x,y)$ 的正整数 $k$，在现有文字之后继续写下 $k$ 行。用式子表示，这次续写会令

一个夜晚结束后，新写下的 $k$ 行便会成为第十二章的一部分。下一个夜晚开始时，你需要使用新的 $x$ 重新计算 $\gcd(x,y)$，再决定接下来能够写下多少行。已经完成的文字不能删去，也不能调整次序，因此每一次选择都会影响余下的续写过程。

你可以用不同的方式安排每个夜晚写下的行数。当 $x=y$ 时，第十二章恰好完成，纸上的旅途也终于在又一次月落前迎来结局。

请你求出完成《月》的第十二章所需的最少夜晚数。

【输入格式】

从文件 $\textbf{\textit{moon.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

接下来 $T$ 行，每行包含一个正整数 $y$，表示一组测试数据。

【输出格式】

输出到文件 $\textbf{\textit{moon.out}}$ 中。

对于每组测试数据，输出一行一个整数，表示你完成第十二章所需的最少夜晚数。

【样例 1 输入】

10 42132412513

【样例 1 输出】

102134412

【说明/提示】

【样例 1 解释】

当 $y=12$ 时，你可以在四个夜晚中依次令 $x$ 变为 $2,3,6,12$。由于每个夜晚结束后 $x$ 至多变为原来的 $2$ 倍，经过三个夜晚后一定有 $x\leq 8$，因此答案为 $4$。

当 $y=13$ 时，对于任意 $1\leq x<13$，均有 $\gcd(x,13)=1$，因此每个夜晚只能写下一行，答案为 $12$。

【样例 2】

见选手目录下的 $\textbf{\textit{moon/moon2.in}}$ 和 $\textbf{\textit{moon/moon2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{moon/moon3.in}}$ 和 $\textbf{\textit{moon/moon3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{moon/moon4.in}}$ 和 $\textbf{\textit{moon/moon4.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{moon/moon5.in}}$ 和 $\textbf{\textit{moon/moon5.ans}}$。

该组样例符合测试点 $13\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10^4$，对于每组测试数据，均有 $1\leq y\leq 10^9$。

特殊性质：对于每组测试数据，$y$ 均为质数。