[ 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 (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⁷).

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