LiveFree loves primes. One day when he was playing with the prime numbers. He wrote first k primes on the board. Then suddenly his friend dracowane comes to his room and saw those primes written on the board. He then gave LiveFree some q queries to solve. Each query contains 2 numbers l and r (l<=r && 1<=l<=r<=k) . In every query query LiveFree has to find the sum of primes from position l to r. Help LiveFree to solve the problem. For more Clarification see the sample input...

Input:

Every test file will contain t test cases. Every test case will contain an integer q denoting the number of queries and every query will contain two integer l and r .

Output:

For every query of each test case print the sum of primes from l to r position in separate lines.

Constraints:

1<=t<=10

1<=q<=10^5

1<=k<=5*10^4

1<=l<=r<=k