Series of roots#3244
Sign in

Series of roots

2 seconds
64 megabytes
Easy

Consider the sum

S = \sum_{x=l}^{r} \lfloor \sqrt{x} \rfloor

where denotes the integer part of .

Given integers and , compute the value of .

Input

The first line contains one integer (1 \le t \le 100\ 000) — the number of test cases. Each of the following lines contains two integers and (1 \le l \le r \le 10^{18}).

Output

For each test case, output the value of in a separate line.

Examples

Example 1

Loading
Loading