提示: 欢迎访问OurACM平台。
Problem 1563 Prime Numbers

Accept: 633    Submit: 1976
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

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.

Input

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.

Output

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

Sample Input

2 2 7 3 1000000

Sample Output

4 78497

Source

FOJ月赛-2007年12月

Submit  Back  Status  Discuss