Bunty has a favorite number $4$. He calls a number his favorite if it has exactly $4$ distinct factors greater than $0$. So Bunty wonders how many favorite numbers are there in the range $[l, r]$. Can you help him find that?

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The only line of each test case contains two space-separated integers - $l$ and $r$.

Output format

For each test case, print an integer - the number of favorite numbers in the given range.

Constraints

$1 ≤ T ≤ 10^5$
$1 ≤ l ≤ r ≤ 10^6$