Square or Cube

Version: Phuoc Hung OJ Extended

Problem Statement

A positive integer is a perfect square if it has the form $k^2$, and a perfect cube if it has the form $t^3$, where $k,t$ are positive integers.

Given two positive integers $L$ and $R$, count the integers $x \in [L,R]$ that satisfy at least one of these conditions: $x$ is a perfect square, or $x$ is a perfect cube.

If a number is both a perfect square and a perfect cube, count it only once.

Input

One line contains two positive integers $L$ and $R$.

Output

Print one integer: the number of values in $[L,R]$ satisfying the requirement.

Subtasks

• Subtask 1 (20%): $1 \le L \le R \le 10^6$.
• Subtask 2 (30%): $1 \le L \le R \le 10^{12}$.
• Subtask 3 (50%): $1 \le L \le R \le 10^{18}$.

Examples

Example 1

Input

1 10

Output

4

Explanation

The required values are $1,4,8,9$. The value $1$ is both a square and a cube, but it is counted once.

Example 2

Input

8 64

Output

8

Explanation

The values are $8,9,16,25,27,36,49,64$. The value $64=8^2=4^3$ belongs to both sets but is counted once.

Example 3

Input

64 729

Output

24

Explanation

The interval contains $20$ perfect squares and $6$ perfect cubes. The values $64=2^6$ and $729=3^6$ are in both sets. By inclusion-exclusion, the number of distinct values is $20+6-2=24$.