Emma is fond of prime numbers. Emma’s teacher gave her an interesting problem to solve. 
The problem is as follows:
The teacher gave Emma 2 positive integers x and y(x ≤ y). 
She asked Emma to find the sum of all the prime numbers between x and y(x and y inclusive).
The teacher gave Emma a few such pairs to calculate the required sum. 
The values of x and y were large and she could not do this task manually, so, Emma came to you 
for help to calculate her answers using a program.
Your task is to help Emma.

INPUT
The first line of input contains the number of test cases, t. 
Then, t lines follow, each containing 2 positive integers x and y, for which you have to find the required sum. 

OUTPUT
The output contains t lines each contains the required sum for that particular test case.
CONSTRAINTS
1 ≤ t ≤ 100000
1 ≤ x ≤ y ≤ 10^6

SAMPLE INPUT
3
1 10
2 6
5 10

SAMPLE OUTPUT
17
10
12
def mysieve(n):
    for i in xrange(2, n):
        if i * i <= n and  not prime[i]:
            for j in xrange(i * i, n, i):
                prime[j] = 1


def comp():
    for i in xrange(2, n):
        if not prime[i]:
            pre[i] = pre[i-1] + i
        else:
            pre[i] = pre[i - 1]

n = 1000001
prime = [0] * n
pre = [0] * n
mysieve(n)
comp()

for _ in xrange(input()):
    a, b = map(int, raw_input().split())
    print pre[b] - pre[a - 1]