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
import math
for t in xrange(int(raw_input())):
    m,n=map(int,raw_input().split())
    s=0
    prime=[1]*(n+1)
    prime[0]=0
    prime[1]=0
    for i in xrange(2,int(math.sqrt(n)+1)):
        if prime[i]:
            for j in xrange(i*i,n+1,i):
                prime[j]=0

    for p in xrange(m,n+1):
        if prime[p]:
            s+=p
            
    print s