Emma is fond of prime numbers. Emma’s teacher gave her an interesting problem to solve.
The problem is as follows:
The teacher gave Emma 2 positive integers x and y(x<=y).
She asked Emma to find the sum of all the prime numbers between x and y(x and y inclusive).
The teacher gave Emma a few such pairs to calculate the required sum.
The values of x and y were large and she could not do this task manually, so, Emma came to you
for help to calculate her answers using a program.
Your task is to help Emma.
INPUT
The first line of input contains the number of test cases, t.
Then, t lines follow, each containing 2 positive integers x and y, for which you have to find the required sum.
OUTPUT
The output contains t lines each contains the required sum for that particular test case.
CONSTRAINTS
1<=t<=100000
1<=x<=y<=106
