Time Limit: 1000 mSec Memory Limit : 32768 KB

Compute the number of prime numbers in a given interval.

A prime number is an integer p greater than 1 whose only positive divisors are 1 and p.

A prime number is an integer p greater than 1 whose only positive divisors are 1 and p.

The first line contains the number of test cases T (T<=1000).

Each test case contains a single line with two numbers separated by a single space: a and b, 2 <= a <= b <= 1000000.

Each test case contains a single line with two numbers separated by a single space: a and b, 2 <= a <= b <= 1000000.

For each test case output a single line, containing the number of primes between a and b inclusive.

2
2 7
3 1000000

4
78497