Sum of Primes in a Range

You are given T test cases. In each test case, you are provided with two integers A and B. Your task is to compute the sum of all prime numbers between A and B (both inclusive).

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. The formula for checking if a number n is prime can be expressed in \( \LaTeX \) as:

\( n \leq 1 \Rightarrow \text{not prime} \)
\( 2 \leq n \leq 3 \Rightarrow \text{prime} \)
\( n \mod 2 = 0 \text{ or } n \mod 3 = 0 \Rightarrow \text{not prime} \)
\( \text{For } i \geq 5, \text{if } n \mod i = 0 \text{ or } n \mod (i+2) = 0 \text{ then } n \text{ is not prime}\)

The solution must read input from stdin and print the results to stdout. Each result should be printed on a new line.

inputFormat

The input begins with an integer T representing the number of test cases. Each of the following T lines contains two space-separated integers A and B (\( A \leq B \)).

Example:

3
5 10
11 20
1 5

outputFormat

For each test case, output the sum of all prime numbers in the interval [A, B] on a separate line.

Example:

12
60
10

## sample

3
5 10
11 20
1 5

12
60
10

</p>