## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Ela's Fitness and the Luxury Number Codeforces Solution

B. Ela's Fitness and the Luxury Number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Since she started engaging in sports activities, Ela switches to trying a new sport on days she considers being "Luxury" days. She counts the days since she started these activities, in which the day she starts is numbered as day

$1$. A "Luxury" day is the day in which the number of this day is a luxurious number.

An integer $x$ is called a luxurious number if it is divisible by $⌊\sqrt{x}⌋$.

Here $⌊r⌋$ denotes the "floor" of a real number $r$. In other words, it's the largest integer not greater than $r$.

For example: $8$$56$$100$ are luxurious numbers, since $8$ is divisible by $⌊\sqrt{8}⌋=⌊2.8284⌋=2$$56$ is divisible $⌊\sqrt{56}⌋=⌊7.4833⌋=7$, and $100$ is divisible by $⌊\sqrt{100}⌋=⌊10⌋=10$, respectively. On the other hand $5$$40$ are not, since $5$ are not divisible by $⌊\sqrt{5}⌋=⌊2.2361⌋=2$, and $40$ are not divisible by $⌊\sqrt{40}⌋=⌊6.3246⌋=6$.

Being a friend of Ela, you want to engage in these fitness activities with her to keep her and yourself accompanied (and have fun together, of course). Between day $l$ and day $r$, you want to know how many times she changes the activities.

Input

Each test contains multiple test cases. The first line has the number of test cases $t$ (). The description of the test cases follows.

Solution Click Below:-  👉
👇👇👇👇👇

The only line of each test case contains two integers $l$ and $r$ ($1\le l\le r\le {10}^{18}$) — the intervals at which you want to know how many times Ela changes her sports.

Output

For each test case, output an integer that denotes the answer.