SP21176 TAP2014I - Stapled intervals

**\[ The original version of this problem (in Spanish) can be found at [http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf](http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf "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 and the set **{a, a+1, ..., b}** is a stapled interval.**

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} $** ).

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.