Description

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.

Input Format

One line with $2$ positive integers $n,k$.

Constraints:

• $2 \le n \le 10^{14}$.
• $1 \le k \le n$.

Output Format

One line with one positive integer, the answer.

3 1

2

6 4

1

Hint

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