CF2233F Shortest GCD Paths

You are given three integers $ n $ , $ a $ , $ b $ . Consider a weighted undirected graph with $ n $ vertices, where for every pair of distinct vertices $ (u, v) $ there is an edge with weight: $$$ w(u, v) = \frac{\max(u, v)}{\gcd(u, v)} $$$ Here $ \gcd(x, y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ . Find the shortest path from vertex $ a $ to vertex $ b $ in this graph.

The only line contains three integers $ n $ , $ a $ , $ b $ ( $ 2 \le n \le 10^{9}, 1 \le a, b \le n, a \neq b $ ).

Print one integer — the length of the shortest path from vertex $ a $ to vertex $ b $ .

Consider the first example. The shortest path in it is $ 9 \to 6 \to 8 $ with total cost $ w(9, 6) + w(6, 8) = 3 + 4 = 7 $ .