Вам даются три целых числа $$$n$$$, $$$a$$$, $$$b$$$. Построим такой взвешенный неориентированный граф, в котором $$$n$$$ вершин и между парой различных вершин с номерами $$$(u, v)$$$ есть ребро с весом:
$$$$$$ w(u, v) = \frac{\max(u, v)}{\gcd(u, v)} $$$$$$
Здесь $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.
Найдите кратчайший путь от вершины $$$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$$$.
