D. Comic Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A comic number is defined as a positive integer which is divisible by the floor of its cubic root (the third root). Example : $$$68$$$ is divisible by $$$\lfloor \sqrt[3]{68} \rfloor = \lfloor 4.081 \rfloor = 4$$$.

Given two positive integers $$$l$$$ and $$$r$$$, $$$(l \le r)$$$, find the total number of comic numbers between them (inclusive of $$$l$$$ and $$$r$$$ both).

Input

The first line of the input contains a single integer $$$t$$$ - the number of testcases.

Each testcase consists of one line containing two positive integers $$$l$$$ and $$$r$$$.

$$$1 \le t \le 10^5$$$.

$$$1 \le l \le r \le 10^{18}$$$.

Output

For each testcase, Print the total number of comic numbers between $$$l$$$ and $$$r$$$, $$$[l, r]$$$ (inclusive) in a newline.

Example
Input
2
1 1000000000000000000
3 81
Output
1500002499997
33