Sum of Primes
Tag(s):

## Easy-Medium, Number Theory

Problem
Editorial
Analytics

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$

SAMPLE INPUT
2
1 6
4 13
SAMPLE OUTPUT
10
36
Explanation

For the $1^{st}$ query, the primes between 1 and 6 are 2, 3 and 5. Thus the answer= $2 + 3 + 5$ = $10$. Similarily, for the second query, Answer = $5 + 7 + 11 + 13$ = $36$.

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...