Count Primes in Range

You are given T test cases. In each test case, you will be provided with two integers A and B. Your task is to count the number of prime numbers in the inclusive range \( [A, B] \).

A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. In other words, a number \( p \) is prime if \( p > 1 \) and \( \forall k \ (2 \le k \le \sqrt{p}),\; p \mod k \neq 0 \).

You are expected to use an efficient algorithm, such as the Sieve of Eratosthenes, to precompute all prime numbers up to the maximum value of B among all test cases. Then, for each test case, count the number of primes in the specified interval using this precomputed list.

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

• The first line contains a single integer T, which is the number of test cases.
• Each of the next T lines contains two space-separated integers A and B representing the range.

outputFormat

For each test case, output a single integer on a new line representing the number of prime numbers in the range \( [A, B] \).

The output should be written to standard output (stdout).

## sample

5
10 20
15 30
1 10
21 29
2 5

4
4
4
2
3

</p>