D. Simplest Fractions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A fraction $$$\frac{a}{b}$$$ ($$$a$$$ and $$$b$$$ are positive integers) is called a simplest fraction if and only if it satisfies the following conditions:

  • $$$a \gt 0$$$, $$$b \gt 1$$$.
  • $$$\gcd(a, b) = 1$$$.

Here $$$\operatorname{gcd}$$$ denotes the greatest common divisor.

You are given two integers $$$l$$$ and $$$r$$$. Find the number of simplest fractions $$$\frac{a}{b}$$$ such that $$$l \le a + b \le r$$$.

Input

The first line of the input will contain a single integer $$$t$$$ $$$(1\le t\le 10^5)$$$, the total number of test cases.

Each test case will contain two integers $$$l$$$ and $$$r$$$ $$$(1 \le l \le r \le 10^{6})$$$.

Note there is no constraint on the sum of $$$l$$$ and $$$r$$$ over all test cases.

Output

Print in a new line  — the number of simplest fractions $$$\frac{a}{b}$$$ that satisfy the condition above.

Example
Input
2
1 3
4 5
Output
1
4
Note

In the first test case, only $$$\frac{1}{2}$$$ satisfies the condition.

In the second test case, $$$\frac{1}{3}$$$, $$$\frac{1}{4}$$$, $$$\frac{2}{3}$$$, and $$$\frac{3}{2}$$$ satisfy the condition.