Prime Counting in Intervals

You are given n messages, where each message represents an interval in the form of two integers a and b. For each interval, count the number of prime numbers in the range \( a \) to \( b \) (inclusive).

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In mathematical terms, a number \( p > 1 \) is prime if and only if it is not divisible by any integer from 2 up to \( \sqrt{p} \). You may use techniques such as the Sieve of Eratosthenes to efficiently generate prime numbers.

Your task is to process the input, compute the result for each interval, and output the counts. Good luck!

inputFormat

The first line contains an integer n representing the number of intervals. Each of the following n lines contains two integers a and b, representing the endpoints of an interval. ( a ) and ( b ) satisfy ( 1 \leq a \leq b ).

outputFormat

For each interval, output a single line containing the number of prime numbers within that interval (inclusive).## sample

3
2 10
11 20
20 30

4
4
2