시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 17 9 9 56.250%

## 문제

A positive integer is called a "prime-factor prime" when the number of its prime factors is prime. For example, 12 is a prime-factor prime because the number of prime factors of 12 = 2 × 2 × 3 is 3, which is prime. On the other hand, 210 is not a prime-factor prime because the number of prime factors of 210 = 2 × 3 × 5 × 7 is 4, which is a composite number.

In this problem, you are given an integer interval [l,r]. Your task is to write a program which counts the number of prime-factor prime numbers in the interval, i.e. the number of prime-factor prime numbers between l and r, inclusive.

## 입력

The input consists of a single test case formatted as follows.

l r

A line contains two integers l and r (1 ≤ lr ≤ 109), which presents an integer interval [l,r]. You can assume that 0 ≤ r - l < 1,000,000.

## 출력

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

## 예제 입력 1

1 9


## 예제 출력 1

4


## 예제 입력 2

10 20


## 예제 출력 2

6


## 예제 입력 3

575 57577


## 예제 출력 3

36172


## 예제 입력 4

180 180


## 예제 출력 4

1


## 예제 입력 5

9900001 10000000


## 예제 출력 5

60997


## 예제 입력 6

999000001 1000000000


## 예제 출력 6

592955


## 힌트

In the first example, there are 4 prime-factor primes in [l,r]: 4, 6, 8, and 9.