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

hide comments
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.


Added by:Fidel Schaposnik
Date:2014-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2014