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
T = input()
import math
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
for t in range(T):
	num_s = raw_input()
	num = map(int,num_s.split())
	lower = num[0]
	upper = num[1]
	total = 0
	for i in xrange(lower,upper+1):
		a = is_prime(i)
		if a == False:
			total = total 
		else:
			total = total + i
	if lower == 1:
		print total - 1
	else :
		print total