Limits 2s, 512 MB

Prime Numbers are such numbers which are only divided by 1 and the number itself. 2, 3, 5, 7, 11, 13 are the first six prime numbers.

In this problem, you will be given the range x and y. You have find out the sum of prime numbers from the x-th prime number to the y-th prime number (inclusive).

Input

In the first line of input, you will take a number n (1 ≤ n ≤ 105) as input. On each of the following n lines, you will take two numbers x and y (1 ≤ Prime[x], Prime[y] ≤ 108) as input.

Output

For each x and y, you have to print the sum of all prime numbers in between the x-th prime number to the y-th prime number (inclusive).

Each output should be printed on a newline.

Sample

InputOutput
2
1 2
3 5
5
23

Submit

Login to submit.

Contributors

Statistics

67% Solution Ratio
shakil007Earliest, May '18
Kuddus.6068Fastest, 0.1s
nusuBotLightest, 47 MB
SpellMasterShortest, 408B
Toph uses cookies. By continuing you agree to our Cookie Policy.