bee 3339 - Karina

Professor Karina usually teaches Discrete Mathematics classes for the Computer Science course. During online classes, she suspected that her students weren't paying attention and decided to take an exam/competition on kahoot.

As the class of the day was about perfect squares, in each test/competition question she would give an interval [L, R] (limits included) and would like to know how many perfect squares exist within the given interval.

Just to remind you, a perfect square is an integer square root number. Ex: 0, 1, 4 and 9.

Input

In the first line, an integer Q is passed representing the number of questions in the test/competition. In the next Q rows there will be two integers L, R in each row representing the limits.

The restrictions for the values are as follows:

\(1 \leq \textbf{Q} \leq 10^3\)
\(0 \leq \textbf{L} \leq \textbf{R} \leq 10^{8}\)

Output

For each question it is necessary to print an integer representing the number of perfect squares within the range [L, R] (limits included).

Input Sample	Output Sample
2 0 64 1 64	9 8

Input Sample

Output Sample

0 64

1 64