As is known to all, a prime number is a number who can only be divided by 1 and itself. For example, 2,3,5 are all prime numbers but 4,6 are not.
Because 4 has another diviser 2, and 6 has two divisers: 2 and 3.
Now the problem is, give you two non-negetive integers, start and end, your work is to tell me the sum of all the prime numbers between start and end(include the start and end).
Input
The first line is an integer T, which means the test cases in the input file, T is no more than 100000
The 2nd to the (T+1)th lines are the cases, for each line, there are two integers start and end, both of them are larger than 0 and smaller than 100000.
Output
For each test case, output one integer for a line, the sum of all the prime numbers in the range.