给你三个整数 $$$n$$$、$$$a$$$、$$$b$$$。考虑一个具有 $$$n$$$ 顶点的加权无向图,其中对于每对不同的顶点 $$$(u, v)$$$ 都有一条具有权重的边:
$$w(u, v) = \frac{\max(u, v)}{\gcd(u, v)}$$
这里 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
在此图中找到从顶点 $$$a$$$ 到顶点 $$$b$$$ 的最短路径。
输入
唯一一行包含三个整数 $$$n$$$、$$$a$$$、$$$b$$$ ($$$2 \le n \le 10^{9}、1 \le a、b \le n、a \neq b$$$)。
输出
打印一个整数——从顶点 $$$a$$$ 到顶点 $$$b$$$ 的最短路径的长度。
示例
输入复制
10 9 8
输出复制
7
输入复制
100 16 27
输出复制
10
输入复制
100 55 11
输出复制
5
注意
考虑第一个例子。
其中最短路径为 $$$9 \to 6 \to 8$$$,总成本 $$$w(9, 6) + w(6, 8) = 3 + 4 = 7$$$。