Tennis Score

Time limit2sMemory limit1024 MB

Summary

Given the final score a:b, find the minimum possible sum of gcd values over every score visited on a path from 0:0 to a:b.

Level: Medium6 of 10
Topics: Number theory, Greedy
Solved: No attempts yet

Statement

Aurora and Notgrass decided to play tennis and asked Flitl to referee. At the start the score was $0 : 0$ . Then, several times, one of the players gained $1$ point. The game ended with the score $a : b$ .

Fislvit was bored, so she computed the sum of the greatest common divisors of the players' points after each change of the score. $\gcd(x, y)$ is the greatest common divisor of two numbers. For example, the game could have gone like this:

$0 : 0$
$1 : 0$ , $\gcd(1, 0) = 1$
$2 : 0$ , $\gcd(2, 0) = 2$
$2 : 1$ , $\gcd(2, 1) = 1$
$2 : 2$ , $\gcd(2, 2) = 2$
$2 : 3$ , $\gcd(2, 3) = 1$

In that case Fislvit's sum would be $1 + 2 + 1 + 2 + 1 = 7$ .

After the game, Fislvit wondered what the smallest possible value of her sum could be. Help her find it.

Input

The input contains two integers $a$ and $b$ on a single line, the final points of Aurora and Notgrass ( $0 \le a, b \le 10^9$ ).

Output

Print one integer, the minimum value that Fislvit's sum could have had.

Examples4

Example 1
Input
```
2 1
```
Expected output
```
3
```
Example 2
Input
```
4 6
```
Expected output
```
11
```
Example 3
Input
```
0 0
```
Expected output
```
0
```
Example 4
Input
```
10 10
```
Expected output
```
31
```