1213 - Prime's Sum Again

Time Limit : 3 Second

Memory Limit : 128 MB

Submission: 118

Solved: 18

As is known to all, a prime number is a number which can only be divided by 1 and itself. For example: 2, 3 and 5 are all prime numbers but 4 and 6 are not, because 4 has another divisor 2, and 6 has two other divisors 2 and 3.
Then the problem is: give you two nonnegative integers L and R, you are asked to tell me the sum of all the prime numbers in the range [L, R). Range [L, R) means all the integers x that L <= x < R.
The first line is an integer T (T <= 200) means the number of the test cases.
The following T lines are the T test cases. For each line, there are two integers L and R, 0 <= L, R <= 1,000,000,000.
For each test case, output a single line with the sum of all the prime numbers in the range [L, R), because the sum is too large, you can only output the last 4 digits of the sum.
sample input
1 10
4 6
14 18
sample output
© 2015 HUST ACMICPC TEAM. All Right Reserved.