Bình phương hoặc lập phương (Square or Cube)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một số nguyên dương là số chính phương nếu có dạng $k^2$, và là số lập phương nếu có dạng $t^3$, trong đó $k,t$ là các số nguyên dương.

Cho hai số nguyên dương $L$ và $R$. Hãy đếm số lượng số nguyên $x \in [L,R]$ thỏa mãn ít nhất một trong hai điều kiện: $x$ là số chính phương hoặc $x$ là số lập phương.

Nếu một số đồng thời là số chính phương và số lập phương thì chỉ được tính một lần.

Input

Một dòng chứa hai số nguyên dương $L$ và $R$.

Output

In ra một số nguyên duy nhất là số lượng số thuộc đoạn $[L,R]$ thỏa mãn yêu cầu.

Subtask

• 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}$.

Ví dụ

Ví dụ 1

Input

1 10

Output

4

Giải thích

Các số thỏa mãn là $1,4,8,9$. Số $1$ vừa là chính phương vừa là lập phương nhưng chỉ được tính một lần.

Ví dụ 2

Input

8 64

Output

8

Giải thích

Các số cần đếm là $8,9,16,25,27,36,49,64$. Số $64=8^2=4^3$ thuộc cả hai nhóm nhưng chỉ tính một lần.

Ví dụ 3

Input

64 729

Output

24

Giải thích

Trong đoạn có $20$ số chính phương và $6$ số lập phương. Hai số $64=2^6$ và $729=3^6$ thuộc cả hai nhóm. Theo nguyên tắc cộng trừ, số lượng phân biệt là $20+6-2=24$.