Odd One Out
Description
Given an integer $X$, let $f(X)$ denote the number of ordered pairs $(a,b)$ such that $\gcd(a,b) \times \text{lcm}(a,b) = X$.
A number $Y$ is beautiful if $f(Y)$ is odd.
Count the number of beautiful numbers that lie in a given range $[L, R]$.
Refer to the notes below if you don't understand some of these terms.
Input starts with an integer $T$ ($1 \leq T \leq 10$), denoting the number of test cases.
Each case starts with a line containing two integers $L$ and $R$ ($1 \le L \le R \le 10^9$).
For each query, you have to print a line containing the number of beautiful numbers in the range $[L,R]$.
Input
Input starts with an integer $T$ ($1 \leq T \leq 10$), denoting the number of test cases.
Each case starts with a line containing two integers $L$ and $R$ ($1 \le L \le R \le 10^9$).
Output
For each query, you have to print a line containing the number of beautiful numbers in the range $[L,R]$.
2
2 8
4669 176420
1
352
Note
The first three beautiful numbers are $1,4,9$.
In the first sample, the only beautiful number which lies between $2$ and $8$ is the number $4$. It is a beautiful number because there are $3$ ordered pairs $(a,b)$ satisfying the equation given in the statement: they are $(1,4),(2,2),(4,1)$. Since this number $3$ is odd, the number $4$ qualifies as beautiful. One can check that the other numbers between $2$ and $8$ do not satisfy these conditions.
Definitions
- An ordered pair $(a, b)$ is a pair where the order in which the elements $a,b$ appear is significant. The ordered pair $(a, b)$ is different from the ordered pair $(b, a)$ unless $a = b$.
- The greatest common divisor $\gcd(a,b)$ of two numbers $a,b$ is the largest number which divides both $a$ and $b$. For example: $\gcd(6, 15)=3$.
- The least common multiply $\text{lcm}(a,b)$ of two numbers $a,b$ is the smallest number that both $a$ and $b$ divide. For example: $\text{lcm}(6,15)=30$.