Underprime

Interview

Time limit2sMemory limit128 MB

Summary

Count integers in a range whose total number of prime factors (with multiplicity) is itself a prime number.

Level: Easy3 of 10
Topics: Number theory, Math, Implementation
Solved: No attempts yet

Problem

When a positive integer X is factorized into primes, we get a list of prime numbers whose product is X. For example, 12 factors as 2 × 2 × 3, so the list has length 3. The number 1 is not prime.

A number X is called an underprime if the length of this prime-factor list is itself prime. Since 12 has a list length of 3 and 3 is prime, 12 is an underprime.

Given two integers A and B, count how many integers from A through B, inclusive, are underprimes.

Input

The first line contains two integers A and B.

Output

Print the number of underprimes greater than or equal to A and less than or equal to B.

Constraints

2 ≤ A ≤ B ≤ 100,000

Examples4

Example 1
Input
```
2 10
```
Expected output
```
5
```
Example 2
Input
```
100 105
```
Expected output
```
2
```
Example 3
Input
```
17 17
```
Expected output
```
0
```
Example 4
Input
```
123 456
```
Expected output
```
217
```