Almost Prime Numbers

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

A positive integer $x$ is called an almost prime number if $x$ is not prime and all of its prime divisors are the same.

Equivalently, $x$ is almost prime if and only if there exist a prime number $p$ and an integer $k\ge2$ such that

For example, $4=2^2$, $8=2^3$, and $9=3^2$ are almost prime numbers, while $6=2\cdot3$ is not.

Given two integers low and high, count the almost prime numbers $x$ satisfying

Input

The only line contains two integers low and high.

Output

Print one integer: the number of almost prime numbers in the closed interval $[low,high]$.

Subtasks

• Subtask 1 — 20%: $1\le low\le high\le10^6$.
• Subtask 2 — 30%: $1\le low\le high\le10^9$.
• Subtask 3 — 50%: $1\le low\le high<10^{12}$.

Example

Input

1 10

Output

3

Explanation

The almost prime numbers in $[1,10]$ are

Hence the answer is $3$.