【XR-3】小道消息

题目描述

小 X 想探究小道消息传播的速度有多快,于是他做了一个社会实验。 有 $n$ 个人,其中第 $i$ 个人的衣服上有一个数 $i+1$。小 X 发现了一个规律:当一个衣服上的数为 $i$ 的人在某一天知道了一条信息,他会在第二天把这条信息告诉衣服上的数为 $j$ 的人,其中 $\gcd(i,j)=1$(即 $i,j$ 的最大公约数为 $1$)。在第 $0$ 天,小 X 把一条小道消息告诉了第 $k$ 个人,小 X 想知道第几天时所有人都会知道这条小道消息。 可以证明,一定存在所有人都知道了这条小道消息的那一天。 提示:你可能需要用到的定理——[伯特兰-切比雪夫定理](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)。

输入输出格式

输入格式


一行 $2$ 个正整数 $n,k$。 **数据范围:** - $2 \le n \le 10^{14}$。 - $1 \le k \le n$。

输出格式


一行一个正整数,表示答案。

输入输出样例

输入样例 #1

3 1

输出样例 #1

2

输入样例 #2

6 4

输出样例 #2

1

说明

【样例 $1$ 说明】 $3$ 个人的衣服上的数分别为 `2 3 4`。 在第 $0$ 天,小 X 把一条小道消息告诉了第 $1$ 个人,他的衣服上的数为2。 在第 $1$ 天,第 $1$ 个人会告诉第 $2$ 个人,因为 $\gcd(2,3) = 1$,但他不会告诉第 $3$ 个人,因为 $\gcd(2,4) = 2 \ne 1$。 在第 $2$ 天,第 $2$ 个人会告诉第 $3$ 个人,因为 $\gcd(3,4) = 1$,这时所有人都知道了这条小道消息,因此答案为 $2$。