Sum of Primes in a Range

This problem requires you to compute the sum of all prime numbers in a given range \([L, R]\) for multiple test cases. You are asked to implement an efficient solution by employing the Sieve of Eratosthenes to generate prime numbers and then use a segmented sieve technique to handle the given range.

Task Details:

• For each test case, you are given two integers \(L\) and \(R\) and you need to output the sum of all primes in the interval \([L, R]\).
• If there are no primes in the range, output 0.
• You must read input from stdin and write your answer to stdout.

Mathematical Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The Sieve of Eratosthenes is an efficient way to find all primes up to a given limit \(n\) using the following recurrence: \[ \text{is\_prime}(p) = \begin{cases} true & \text{if } p \text{ has no divisors less than } \sqrt{n} \\ false & \text{otherwise} \end{cases} \]

inputFormat

The first line of input contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains two space-separated integers \(L\) and \(R\), representing the range (inclusive) for which the sum of prime numbers is to be computed.

Sample Input:
3
1 10
11 20
21 30

outputFormat

For each test case, output the sum of the prime numbers in the range \([L, R]\) on a separate line.

Sample Output:
17
60
52

## sample

3
1 10
11 20
21 30

17
60
52

</p>