Problems
Vasya and prime numbers
Vasya and prime numbers
Vasya learned at math lesson that prime number is a positive integer that is divisible only by 1 and itself, and the number 1 is not a prime. Vasya knows that Pete likes to give a lot of questions like "from l to r". Vasya found himself a new task: count the number of primes in the interval from l to r.
Input data
Consists of multiple test cases. Each test contains on a separate line two (possibly negative) integers l and r (l ≤ r, |l|, |r| < 10^6
). The last line contains two numbers -1 and is not processed.
Output data
For each test case print on a separate line the number of primes from l to r.
Examples
Input example #1
4 10 0 5 -1 -1
Output example #1
2 3
Input example #2
10 20 -555 3 -1 -1
Output example #2
4 2