Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Prime Range

By tahmedge, ishtupeed · 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

Discussion

Statistics


70% Solution Ratio

shakil007Earliest, May '18

nishatFastest, 0.3s

fsshakkhorLightest, 48 MB

sorcererShortest, 527B

Submit

Login to submit