## TAP2014I - Stapled intervals

no tags

[ The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.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 ( 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 ( A  B  107).

### Output

Print P lines, each with a single integer number. For i = 1, 2, ..., P the number in the i-th line represents the number of stapled intervals completely contained in the range [A, B] corresponding to the i-th question.

### Example

```Input:
4
2184 2200
2185 2200
2184 2199
1 100000

Output:
1
0
0
13
``` S.Y.P.Lai: 2014-10-26 15:07:48 Well, source limit = 50000B ... OK! Thank you! Fidel Schaposnik: 2014-10-03 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). [2185,2200] is not a stapled interval because 2197 is coprime to all other numbers in that range. Same thing goes for [2184,2199] with 2189, so the answer to queries 2 and 3 is 0 (because again they don't contain any other stapled interval). The answer to the 4th query is 13 because there are 13 different stapled intervals contained in the range [1,10^5]. Rahul Jain: 2014-10-02 01:10:41 Can u please explain the output.