P8302 [CoE R4 B/Stoi2041] 龙拳


对于 $n \in \mathbb{Z_{\ge 2}}$，设 $g(n)$ 为 $n$ 的小于 $n$ 的最大约数，如 $g(7) = 1, g(12) = 6$。 定义 $f(n) = n + g(n)$。记 $f^{(0)}(n)=n$，且对 $m \in \mathbb{Z_{\ge 0}}$ 有 $f^{(m+1)}(n)=f(f^{(m)}(n))$。 多次询问，每次询问给定正整数 $n,k$，求最小的自然数 $m_0$，使得对于任意 $m \ge m_0$，均有 $f^{(m)}(n) \mid f^{(m+k)}(n)$。 若不存在这样的 $m_0$，则令 $m_0=-1$。

无

无

### 样例解释 当 $n=2,k=3$ 时，$m_0=0$。 当 $n=3,k=4$ 时不存在满足条件的 $m_0$。 --- ### 数据规模 **本题采用捆绑测试。** - 子任务 $1$（$1$ 分）：$T=k=1$； - 子任务 $2$（$12$ 分）：$T,n,k \le 10$； - 子任务 $3$（$24$ 分）：$T \le 10,n \le 10^5$； - 子任务 $4$（$36$ 分）：$T \le 10^3$； - 子任务 $5$（$27$ 分）：无特殊限制。 对于 $100\%$ 的数据，保证 $1 \le T \le 2 \times 10^6$，$2 \le n \le 3 \times 10^7$，$1 \le k \le 10^9$。