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
t = int(raw_input().strip())
import math

P = [1]*1000001
P[1] = 0
P[0] = 0
def sieve():
	for i in range(2, int(math.sqrt(1000000))+1):
		if P[i]:
			for j in range(i*i, 1000001, i):
				P[j] = 0
				
	# Prefix sum:
	#for i in range(1, 1000001):
	#		if P[i]:
	#		P[i] = P[i-1] + i
	#	else:
	#		P[i] = P[i-1]


while t:
	t-=1
	
	sieve()
	x, y = map(int, raw_input().strip().split(" "))
	s = 0
	for i in range(x, y+1):
		if P[i]:
			s += i
	print s