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).
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.
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.
2 1 2 3 5