MMFMOB2 - Möbius function zero distribution


In number theory and combinatorics Möbius function μ(n) for integer n > 0 is defined as follows:

μ(1) = 1
μ(n) = (-1)k if n is the product of k (k > 0) distinct primes
μ(n) = 0 otherwise.

Let's define integer n > 0 as nfr point of Möbius function if μ(n) = 0. Given closed interval [a, b] compute number of nfr points from this interval.

Input

Each line of input contains two space separated random integer numbers a and b (1 ≤ a ≤ b ≤ 100 000 000). Input terminates with two space separated 0 (zero). There will be one input file.

Output

For each pair print required value on new line.

Example

Input:
1 1
2 4
3 7
4 10
5 9
6 10
0 0

Output:
0
1
1
3
2
2

hide comments
sanchit_aga: 2019-01-21 14:23:56

Nice problem sir.


Added by:julkas
Date:2018-05-16
Time limit:60s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All