Numere magice

Gomory has just studied Goldbach’s conjecture, which sparked his interest in prime numbers. Now, together with Hu, he is asking several questions related to numbers contained in certain intervals.

Task

You are given multiple queries of the form: “How many numbers with $3$ odd divisors are in the range $[l,r]$?”.
You must output the answer to each query, on a separate line.

Input Data

From the first line, an integer $Q$ will be read, representing the number of queries.

From each of the next $Q$ lines, two numbers separated by a space will be read, the first representing the left endpoint of the query, and the second representing the right endpoint of the query.

Output Data

You must output $Q$ lines. The $i$-th line must contain a single number representing the answer to the $i$-th query.

Constraints

• $Q \leq 10\,000$
• $1 \leq l_i \leq r_i \leq 10^{12}$, for each $i$ from $1$ to $Q$

Example

stdin

1
1 20

stdout

2

Explanation

In the range $[1,\ 20]$ there are only two numbers with $3$ odd divisors. These are 9 and 18. Their divisors are: $1$, $3$, $9$; respectively: $1$, $2$, $3$, $6$, $9$, $18$.