Let's define the function $F(l,r)$ :

$F(l,r)$ = $\sum x$, $\forall x$, where x is a prime number between l and r inclusive.

In Short, for each function $F(l,r)$ you need to find the summation of all primes between the integers l and r inclusive.

Now, you shall be given multiple queries. In each query, you shall be given the integers l and r and you need to find the result of the function $F(l,r)$

Input Format:

The first line contains a single integer N denoting the number of queries. Each of the next N lines contains two integers l and r denoting the parameters of the $i^{th}$ query.

Output Format:

For each query, output the answer on a new line.

Constraints

For $30$ Points:

$1 \leq N \leq 1000$

$1 \leq l \leq r \leq 1000$

For the next $70$ Points:

$1 \leq N \leq 5*10^5$

$1 \le l \le r \le 10^6$