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
def prime():
	import math
	for _ in xrange(input()):
		a, b = map(int, raw_input().split())
		sum = 0
		if a == 1 and b != 1:
			a = 2
		elif a == 1 and b == 1:
			print '0'
			continue
		if a == 2:
			sum += 2
			a = 3
			
		for i in xrange(a, b+1):
			
			flag = 0
			for j in xrange(2,int(math.sqrt(i)+1)):
				if i%j == 0:
					flag = 1
					break
			
			if flag == 0:
				sum += i
				
			
		print sum

if __name__ == "__main__":
	prime()