Counting Prime Numbers in a Range

You are given several queries, each consisting of two integers L and R. Your task is to count the number of prime numbers in the interval \([L, R]\) (both inclusive).

To solve this problem efficiently, you are advised to use the Sieve of Eratosthenes algorithm. In this algorithm, you precompute an array \(prime[0 \ldots n]\) where:

[ prime[i] = \begin{cases} \text{True} & \text{if } i \text{ is prime}, \ \text{False} & \text{otherwise}. \end{cases} ]

Once the sieve is generated, you can process each query by counting the number of indices \(i\) in the range \([L, R]\) for which prime[i] is true.

Input Format: The first line contains an integer T representing the number of queries. Each of the following T lines contains two integers L and R separated by space.

Output Format: For each query, print the count of prime numbers in the given range in a new line.

inputFormat

The input will be given via standard input (stdin):

1. The first line contains one integer T, representing the number of queries.
2. The next T lines each contain two space-separated integers L and R representing the range.

outputFormat

For each query, output a single integer which is the number of prime numbers in the range \([L, R]\), each on its own line. The output should be written to standard output (stdout).

## sample

3
1 10
11 20
1 20

4
4
8

</p>