Karan's mathematics professor has given him a lots of homework. Since he is busy preparing for September Easy Challenge, he needs your help.

Given two numbers, find the sum of prime numbers between them, both inclusive. 

Input:

The first line contains the number of test cases T. Each test case contains two space separated integers.

Output:

Print the answer on a new line for each case.

Constraints:

1 ≤ T ≤ 100

1 ≤ a,b < 10^6

SAMPLE INPUT
1
1 5

SAMPLE OUTPUT
10
'''
Sum of primes in a range
'''

LIMIT = 10**6
NUMBERS = [True] * LIMIT
NUMBERS[0] = NUMBERS[1] = False

for (i, isprime) in enumerate(NUMBERS):
    if isprime:
        # starting the non-prime marking at the prime's square (i*i) instead of its double.
        # Mark factors non-prime
        for number in xrange(i*i, LIMIT, i):
            NUMBERS[number] = False

if __name__ == '__main__':
    for _ in range(int(raw_input())):
        a, b = map(int, raw_input().split())
        print sum(a + num for num, isPrime in enumerate(NUMBERS[a:b + 1]) if isPrime)