[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$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 ⌊𝑥‾‾√⌋$\lfloor \sqrt{x}\rfloor$.

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

For example: 8$8$, 56$56$, 100$100$ are luxurious numbers, since 8$8$ is divisible by ⌊8‾√⌋=⌊2.8284⌋=2$\lfloor \sqrt{8}\rfloor =\lfloor 2.8284\rfloor =2$, 56$56$ is divisible ⌊56‾‾‾√⌋=⌊7.4833⌋=7$\lfloor \sqrt{56}\rfloor =\lfloor 7.4833\rfloor =7$, and 100$100$ is divisible by ⌊100‾‾‾‾√⌋=⌊10⌋=10$\lfloor \sqrt{100}\rfloor =\lfloor 10\rfloor =10$, respectively. On the other hand 5$5$, 40$40$ are not, since 5$5$ are not divisible by ⌊5‾√⌋=⌊2.2361⌋=2$\lfloor \sqrt{5}\rfloor =\lfloor 2.2361\rfloor =2$, and 40$40$ are not divisible by ⌊40‾‾‾√⌋=⌊6.3246⌋=6$\lfloor \sqrt{40}\rfloor =\lfloor 6.3246\rfloor =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$ (1≤𝑡≤10 000$1\le t\le 10000$). The description of the test cases follows.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The only line of each test case contains two integers 𝑙$l$ and 𝑟$r$ (1≤𝑙≤𝑟≤1018$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.