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
__author__ = 'josebib'
def is_prime(n):
    if n==1:
         return False
    if n % 2 == 0 and n > 2:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True
def add(f,s):
    sum=0
    for nos in range(f,s+1):
       
        if is_prime(nos):
            sum+=nos
    return sum

i=input()
for inputs in range(i):
    f,s=raw_input().split(" ")
    print add(int(f),int(s))