Sum of Primes 2

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.6s
Memory limit: 64M

Author:
Problem type

Bob needs to do a lot of practice with prime numbers for homework. Being a curious student, he will ask you Q questions. Each of these questions will be of the form: what is the sum of all prime numbers between A and B (inclusive)?

Input Specification

The first line contains a single integer: Q

Each of the next Q lines contains two space-separated integers: A, B

Output Specification

Output the answer to each question on a separate line.

Constraints

1 \le Q \le 10^5

1 \le A \le B \le 10^5

Subtasks

Subtask 1 [20%]

1 \le Q \le 1000

1 \le A \le B \le 1000

Subtask 2 [80%]

No additional constraints.

Sample Input

3
1 2
5 11
3 19

Sample Output

2
23
75

Comments