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\)