TAP2014I  Stapled intervals
[ The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014problems.pdf ]
Two natural numbers n and m are said to be coprime if their greatest common divisor is the number 1. In other words, n and m are coprime if there is no integer d > 1 such that d exactly divides both n and m. A finite set of two or more consecutive natural numbers is called a "stapled interval" if there is no number in it that is coprime to all other numbers in the set.
Given a range [A, B], we would like to count the number of stapled intervals completely contained in it. I.e., we want to know how many different pairs (a, b) exist such that A ≤ a < b ≤ B and the set {a, a+1, ..., b} is a stapled interval.
Input
The first line contains an integer P representing the number of questions you should answer (1 ≤ P ≤ 1000). Each of the following P lines describes a question, and contains two integer numbers A and B representing the borders of the range [A, B] in which we want to count stapled intervals (1 ≤ A ≤ B ≤ 10^{7}).
Output
Print P lines, each with a single integer number. For i = 1, 2, ..., P the number in the ith line represents the number of stapled intervals completely contained in the range [A, B] corresponding to the ith question.
Example
Input: 4 2184 2200 2185 2200 2184 2199 1 100000 Output: 1 0 0 13
hide comments
S.Y.P.Lai:
20141026 15:07:48
Well, source limit = 50000B ... OK! Thank you! 

Fidel Schaposnik:
20141003 16:10:14
[2184,2200] is a stapled interval as defined in the problem statement, then the answer to the first query is 1 (because it does not contain any other stapled interval).


Rahul Jain:
20141002 01:10:41
Can u please explain the output. 
Added by:  Fidel Schaposnik 
Date:  20140929 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Argentinian Programming Tournament 2014 