eolymp
bolt
Try our new interface for solving problems
Problems

Vasya and prime numbers

Vasya and prime numbers

Time limit 1 second
Memory limit 129 MiB

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 (lr, |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

Author Анатолий Присяжнюк
Source Open and Distance Olympiads 2011-2012