P8302 [CoE R4 B/Stoi2041] Dragon Fist


For $n \in \mathbb{Z_{\ge 2}}$, let $g(n)$ be the largest proper divisor of $n$ (the largest divisor less than $n$), for example, $g(7) = 1, g(12) = 6$. Define $f(n) = n + g(n)$. Let $f^{(0)}(n)=n$, and for $m \in \mathbb{Z_{\ge 0}}$ we have $f^{(m+1)}(n)=f(f^{(m)}(n))$. There are multiple queries. For each query, given positive integers $n,k$, find the smallest natural number $m_0$ such that for any $m \ge m_0$, we always have $f^{(m)}(n) \mid f^{(m+k)}(n)$. If such an $m_0$ does not exist, let $m_0=-1$.

The first line contains a positive integer $T$, the number of queries. The next $T$ lines each contain two positive integers $n,k$, representing one query.

For each query, output one integer as the answer.

### Sample Explanation When $n=2,k=3$, $m_0=0$. When $n=3,k=4$, there is no $m_0$ that satisfies the condition. --- ### Constraints **This problem uses bundled testdata.** - Subtask $1$ ($1$ point): $T=k=1$. - Subtask $2$ ($12$ points): $T,n,k \le 10$. - Subtask $3$ ($24$ points): $T \le 10,n \le 10^5$. - Subtask $4$ ($36$ points): $T \le 10^3$. - Subtask $5$ ($27$ points): no special constraints. For $100\%$ of the data, it is guaranteed that $1 \le T \le 2 \times 10^6$, $2 \le n \le 3 \times 10^7$, $1 \le k \le 10^9$. Translated by ChatGPT 5