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):
	t = 0
	for i in range(2, int(math.sqrt(n)+1)):
		if n%i==0:
			return 0
	return n

t = int(input())
while t>0:
	t = t-1
	a = []
	sm = 0
	s,e = map(int,raw_input().split(" "))
	if s>=1 and e>1:
		for i in range(s,e+1):
			if i>2:
				#print "i=",i
				#print prime(i)
				sm = sm+prime(i)
				#print sm
			elif i==2:
				sm=sm+2
	print sm