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 prime(n):
	ans=1
	for i in range(2,int(math.sqrt(n))+1):
		if n%i==0:
			ans=0
			break
	return ans
t=input()
for i in range(0,t):
	p=raw_input()
	s=0
	a,b=[int(j) for j in p.split()]
	for j in range(a,b+1):
		if(j%2!=0 and j>2):
			ans=prime(j)
			if(ans==1):
				s=s+j
		if j==2	:
			s=s+j
	print s