Count Primes in Given Ranges

You are given T queries. Each query consists of two integers l and r (with 1 ≤ l ≤ r). For each query, you need to count the number of prime numbers in the inclusive range \( [l, r] \).

To solve this problem efficiently, you should first preprocess the prime numbers up to the maximum r among all queries using the Sieve of Eratosthenes. Let the function preprocess_sieve(n) compute an array \( \text{prime\_count} \) where \( \text{prime\_count}[i] \) is the number of prime numbers from 1 to \( i \). Then, using this precomputed array, you can answer each query in constant time using the formula:

[ \text{count} = \text{prime_count}[r] - \text{prime_count}[l-1] ]

Assume that the lower limit l is at least 1. Your program should read input from stdin and write the answer for each query on a new line to stdout.

inputFormat

The first line contains an integer T, the number of queries. Each of the following T lines contains two space-separated integers l and r representing a query.

outputFormat

For each query, output a single integer representing the number of prime numbers in the inclusive range \( [l, r] \). Each result should be printed on a new line.

## sample

3
2 10
11 20
1 100

4
4
25

</p>