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_gen(ma):
  c=range(3, ma+1, 2)
  i=0
  while c[i]<(ma+1)**0.5:
    j=i+1
    while j<len(c):
      if c[j] % c[i] == 0: del c[j]
      j+=1
    i+=1
  return [2]+c

tc = int(raw_input())
max = 0
queries = []
for i in range(tc):
	l,r = map(int,raw_input().split())
	queries.append( (l,r))
	if r>max:
		max=r

primes_list = prime_gen(max)

for l,r in queries:
	s = 0
	for el in primes_list:
		if el>=l and el<=r:
			s+=el
	print s