In this problem, we will say that a pair of integer numbers (x, y) is cool
if y = x + 1, and both x and y are perfect squares or perfect cubes.
For instance, (8, 9) is a cool pair,
because x is a perfect cube (8 = 2^{3})
and y is a perfect square (9 = 3^{2}).
As another example, (0, 1) is a cool pair as well
(a bit special, since 0 and 1 are perfect squares and also perfect cubes).

Given an interval [ℓ, r], how many cool pairs does it contain?

Input

Input consists of several cases,
each one with ℓ and r.
Assume 0 ≤ ℓ < r ≤ 10^{18}.

Output

For every case, print the number of cool pairs with x and y inside [ℓ, r].

Public test cases

**Input**

0 8 0 9 1 15 999999999999999999 1000000000000000000

**Output**

1 2 1 0

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Setzè Concurs de Programació de la UPC - Semifinal
- Date
- 2018-06-20