P5535 [XR-3] Rumors

Xiao X wants to study how fast a rumor spreads, so he did a social experiment. There are $n$ people. The number on person $i$'s clothes is $i+1$. Xiao X found a rule: if a person whose clothing number is $i$ learns a piece of information on some day, then on the next day he will tell this information to every person whose clothing number is $j$ such that $\gcd(i,j)=1$ (that is, the greatest common divisor of $i$ and $j$ is $1$). On day $0$, Xiao X tells a rumor to the $k$-th person. Xiao X wants to know on which day everyone will know this rumor. It can be proven that such a day when everyone knows the rumor must exist. Hint: You may need the following theorem — [Bertrand–Chebyshev theorem](https://baike.baidu.com/item/%E4%BC%AF%E7%89%B9%E5%85%B0-%E5%88%87%E6%AF%94%E9%9B%AA%E5%A4%AB%E5%AE%9A%E7%90%86/2053704).

One line with $2$ positive integers $n,k$. **Constraints:** - $2 \le n \le 10^{14}$. - $1 \le k \le n$.

One line with one positive integer, the answer.

**Explanation for Sample $1$** The clothing numbers of the $3$ people are `2 3 4`. On day $0$, Xiao X tells a rumor to person $1$, whose clothing number is $2$. On day $1$, person $1$ will tell person $2$ because $\gcd(2,3)=1$, but he will not tell person $3$ because $\gcd(2,4)=2 \ne 1$. On day $2$, person $2$ will tell person $3$ because $\gcd(3,4)=1$. Now everyone knows the rumor, so the answer is $2$. Translated by ChatGPT 5