# Tuenti Challenge 5

## Challenge 2 - Almost prime

A composite number is a positive integer that has at least one positive divisor other than one or the number itself. In other words, a composite number is any positive integer greater than one that is not a prime number.
For example, 14 = 2*7 and 18 = 2*3*3 are composite numbers.

We will say a number is "almost prime" if it has exactly two (not necessarily distinct) prime factors.

For example, the following numbers are almost prime: 6 = 2*3, 25 = 5*5. And the following numbers are not: 17 (prime), 81 = 3*3*3*3.

### Input

The first line contains an integer T, the number of test cases. T lines follow, containing two integers each: A and B, separated by a space.

### Output

For each test case, print the number of almost prime numbers P that verify A ≤ P ≤ B.

### Constraints

```1 ≤ T ≤ 100
1 ≤ A ≤ B ≤ 10^8```

```2
1 10
10 20
```

```4
3
```

### Problem stats

Completion time: 10 percentile: 0:60 h 90 percentile: 45:55 h min: 7.00 s 10 percentile: 26.00 s 90 percentile: 32986.67 s max: 214264.87 s min: 1 10 percentile: 1 90 percentile: 7 max: 90 412