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 \)