시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB110595762.637%

문제

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.