Number Strength

Time limit1sMemory limit128 MB

Summary

Given a huge range [A,B] with B up to 1e17, sum the lengths of chains formed by repeatedly replacing N with the smallest integer not dividing it until reaching 2.

Level: Hard8 of 10
Topics: Math, Number theory, Simulation
Solved: No attempts yet

Problem

For a positive integer N, find the smallest positive integer that does not divide N. Replace N with that value and repeat the same process. Stop as soon as N becomes 2.

For example, when N = 6, the number 6 is divisible by 1, 2, and 3, but not by 4, so the next value is 4. Then 4 changes to 3, and 3 changes to 2, producing the sequence 6, 4, 3, 2.

Define strength(N) as the length of the sequence produced by this process. Therefore, strength(6) = 4.

Given two positive integers A < B, compute the sum of number strengths for every integer from A through B, inclusive.

strength(A) + strength(A+1) + ... + strength(B)

Input

The first line contains two integers A and B. (3 <= A < B < 10^17)

Output

Print the sum of number strengths for all integers from A through B, inclusive.

Examples2

Example 1
Input
```
3 6
```
Expected output
```
11
```
Example 2
Input
```
100 200
```
Expected output
```
262
```