Arithmetic derivative P86263

Given a natural number n, its arithmetic derivative d(n) is defined as follows:

• d(0) = d(1) = 0.
• If n is prime, then d(n) = 1.
• Let n = x · y, with 1 < x, y < n. Then d(n) = x · d(y) + y · d(x).

For instance, d(4) = 2d(2) + 2d(2) = 2 + 2 = 4, and d(6) = 3d(2) + 2d(3) = 3 + 2 = 5. It can be proven that this definition is consistent. For example, d(12) = 4d(3) + 3d(4) = 4 + 12 = 16, and also d(12) = 6d(2) + 2d(6) = 6 + 10 = 16.

We say that f is a fixed point of d(n) if d(f) = f. For instance, 0 and 4 are fixed points. Given ℓ and r, can you compute the number of fixed points of d(n) in [ℓ..r]?

Input

Input consists of several cases, each one with ℓ and r, with 0 ≤ ℓ ≤ r ≤ 10¹⁸.

Output

For each case, print the number of fixed points of d(n) in [ℓ..r].