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 generate():
	N = 10**6+1
	mul = set()
	for i in xrange(2, N):
		if i not in mul:
			yield i
			mul.update(range(i*i, N, i))


primes = [i for i in generate()]
kk = [primes[0]]
for i in primes[1:]:
	kk.append(kk[-1] + i)
prime = set(primes)

T = input()
for i in xrange(T):
	L, R = map(int, raw_input().strip().split())
	vals = prime.intersection(range(L, R+1))
	if not vals:
		print 0
	else:
		MIN = min(vals)
		MAX = max(vals)

		MIN_id = primes.index(MIN)
		MAX_id = primes.index(MAX)
		if MIN_id == 0:
			print kk[MAX_id]
		else:
			print kk[MAX_id] - kk[MIN_id-1]