Count Prime Numbers in Ranges

You are given T test cases. In each test case, you are given two integers L and R and you need to count how many prime numbers are in the interval [L, R] (inclusive).

This problem can be efficiently solved by using the Sieve of Eratosthenes algorithm. Specifically, you will compute a sieve up to the maximum R among all test cases to filter out non-prime numbers and then simply count the primes in the specified ranges.

Recall that a number p is prime if it is greater than 1 and has no divisors other than 1 and itself. In mathematical notation, if you denote the primality indicator by \( \pi(n) \) (where \( \pi(n)=1 \) if n is prime and 0 otherwise), then for each test case you are to compute:

[ \text{Count} = \sum_{n=L}^{R} \pi(n) ]

inputFormat

The first line contains an integer T representing the number of test cases.

Each of the following T lines contains two space-separated integers L and R indicating the range [L, R] for that test case.

outputFormat

For each test case, output a single integer in a separate line representing the count of prime numbers in the range [L, R].

## sample

2
1 10
11 20

4
4

</p>