HUST Past Monthly Hard Problems Challenge Contest (1)
From: 20110513 12:00:00
To: 20110513 17:00:00
Now: 20170920 01:10:07
Status: Public
F  Prime's Sum Again
Time Limit: 3s
Memory Limit: 128MB
Submissions: 118 Solved: 18
 Description
 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.
 Input
 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.
 Output
 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

3
1 10
4 6
14 18
 Sample Output

0017
0005
0017
 Hint
 Source