ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2015

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Interesting Numbers

Time limit: 2.0 second
Memory limit: 64 MB
Nikolay and Asya investigate integers together in their spare time. Nikolay thinks an integer is interesting if it is a prime number. However, Asya thinks an integer is interesting if the amount of its positive divisors is a prime number (e.g., number 1 has one divisor and number 10 has four divisors).
Nikolay and Asya are happy when their tastes about some integer are common. On the other hand, they are really upset when their tastes differ. They call an integer satisfying if they both consider or do not consider this integer to be interesting. Nikolay and Asya are going to investigate numbers from segment [L; R] this weekend. So they ask you to calculate the number of satisfying integers from this segment.

Input

In the only line there are two integers L and R (2 ≤ LR ≤ 1012).

Output

In the only line output one integer — the number of satisfying integers from segment [L; R].

Samples

inputoutput
3 7
4
2 2
1
77 1010
924
Problem Author: Alexey Danilyuk
Problem Source: Ural Regional School Programming Contest 2015
To submit the solution for this problem go to the Problem set: 2070. Interesting Numbers