F. Кратчайшие НОД-пути
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даются три целых числа $$$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$$$.