eolymp
bolt
Try our new interface for solving problems
Problems

Some of the roots

Some of the roots

Time limit 2 seconds
Memory limit 64 MiB

Given the sum , where x – the integer part of x. Required by the given numbers l and r to calculate the value of this amount.

Input data

The first line of the input file contains the number of tests t (1t100000). Each test contains a pair of integers l, r (1lr10^18).

Output data

For each test should take only a single line number that is the answer to the problem.

Examples

Input example #1
4
1 2
1 5
2 4
9 10
Output example #1
2
7
4
6
Author Evgeniy Sluzhaev