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 ≤ 10^6

SAMPLE INPUT
3
1 10
2 6
5 10

SAMPLE OUTPUT
17
10
12

见题面

见题面