[HackerEarth] Let's define the function F(l,r) : - P16019

题目描述

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 ≤q N ≤q 1000

1 ≤q l ≤q r ≤q 1000

For the next 70 Points:

1 ≤q N ≤q 5*10^5

1 ≤ l ≤ r ≤ 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.

输入格式

见题面

输出格式

见题面

样例输入

样例输出

时间限制	2000 ms
内存限制	256 MB
难度	普及-
提交数	0
通过数	0
通过率	0.0%

P16019 [HackerEarth] Let's define the function F(l,r) :

题目描述

输入格式

输出格式

样例输入

样例输出