C. Odd One Out
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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]$$$.

Example
Input
2
2 8
4669 176420
Output
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$$$.