Almost Prime Numbers#1302
A positive integer is called almost prime if it is non-prime and divisible by only one prime number.
Determine the number of almost prime numbers within a given interval of positive integers.
The first line contains the number of test cases (n \leq 600).
Each of the following lines represents a separate test case and contains two numbers and (low > 0, low \leq high < 10^{12}).
For each test case, print the number of almost prime numbers in the interval [low \dots high], inclusive.
Example 1