Prime-Factor Prime

Time limit2sMemory limit512 MB

Summary

Count integers in [l, r] whose number of prime factors counted with multiplicity, written Omega(n), is itself prime.

Level: Medium6 of 10
Topics: Number theory, Math, Array, Brute force
Solved: No attempts yet

Problem

A positive integer $n$ is a prime-factor prime when the number of its prime factors, counted with multiplicity, is itself prime. For example, 12 is a prime-factor prime: $12 = 2 \times 2 \times 3$ has 3 prime factors and 3 is prime. 210 is not a prime-factor prime, because $210 = 2 \times 3 \times 5 \times 7$ has 4 prime factors and 4 is composite.

You are given an integer interval $[l, r]$ . Write a program that counts the prime-factor primes in that interval, that is, the prime-factor primes $n$ with $l \le n \le r$ .

Input

The input consists of a single test case in the following format.

l r

One line contains two integers $l$ and $r$ ( $1 \le l \le r \le 10^9$ , $0 \le r - l < 10^6$ ) describing the integer interval $[l, r]$ .

Output

Print the number of prime-factor primes in $[l, r]$ .

Hint

In the first example the prime-factor primes in $[1, 9]$ are 4, 6, 8 and 9, so the answer is 4.

Examples6

Example 1
Input
```
1 9
```
Expected output
```
4
```
Example 2
Input
```
10 20
```
Expected output
```
6
```
Example 3
Input
```
575 57577
```
Expected output
```
36172
```
Example 4
Input
```
180 180
```
Expected output
```
1
```
Example 5
Input
```
9900001 10000000
```
Expected output
```
60997
```
Example 6
Input
```
999000001 1000000000
```
Expected output
```
592955
```