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

def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            n = 0
            break
    return n

t = int(raw_input())
for i in range(0, t):
    s = raw_input()
    s = s.split()
    sum = 0
    if int(s[1]) < 2:
        sum = 0
    if int(s[0]) < 2:
        s[0] = "2"
    for j in range(int(s[0]), int(s[1])+1):
        sum = sum + is_prime(j)
    print sum