You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

即使阳了的学长也必须坚持干活~

Description

众所周知，罗学长和他的队友姜学长被安排到办公室里工作，随着工作的熟练，他们的效率也随着时间的推移而提高。在第1天，他们只能完成1项任务，接下来的2天（第2-第3天），他们可以完成2项任务，再接下来的3天（第4-第6天），他们可以完成3项任务。……以此类推，再接下来的n天可以完成n项任务。学长们希望聪明的你可以帮忙计算一下，在给定的[L,R]区间的时间内，他们一共完成了几项任务？

Format

Input

输入一个数字q，表示询问次数
此后q行，每行输入两个数字L,R。表示查询的时间的起点和终点

Output

输出q行，每行一个数。表示该区间的时间内可以完成的任务总数

Samples

5
1 1
1 2
1 3
1 4
1 5

1
3
5
8
11

Limitation

1s, 1024KiB for each test case.

Special Engagements

对于30%的数据，q≤10000，l,r≤100000
对于70%的数据，q≤1000000，l,r≤10000000
对于100%的数据，q≤10e6,l,r≤10e12 最终的结果不超过 2e63