Counting Prime Number

1000ms    65536K
878    167
Easier

Description

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.
You task is to count how many prime numbers between two integers.

Input

There are multiple test cases. The first line is an integer C, the number of case.
The following C line. Each line has two integers M, N.( 1 < M ≤ N < 1000000)

Output

For each test case output the number of prime between M and N(include M,N).
The last line output "END".

Sample Input

3
5 10
2 3
6 8

Sample Output

2
2
1
END

Source

Editor

keefo on 2013-11-30 21:02:30


North University of China

OnlineJudge

NUC

NOJ

OJ

ACM/ICPC