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) 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).