# Counting Prime Number

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.

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）

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".

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