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
n=input()
a=[]
for i in xrange(n):
	a.append(raw_input())
b=[]
for i in xrange(n):
	b=a[i].split()
	p=0
	for j in xrange(long(b[0]),long(b[1])+1):
		prime=0
		if j>1:
			s=long(math.sqrt(j))
			for k in xrange(2,s+1):				
					if j%k==0:
						prime=1
						break
			if prime==0:
				p=p+j		
	print p