#P1505. F.123

F.123

Background

2021年蓝桥杯国赛F题

Description

小蓝发现了一个有趣的数列,这个数列的前几项如下: 1,1,2,1,2,3,1,2,3,4,1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …

小蓝发现,这个数列前 11 项是整数 11,接下来 22 项是整数 1122,接下来

33 项是整数 1133,接下来 44 项是整数 1144,依次类推。

小蓝想知道,这个数列中,连续一段的和是多少。

Format

Input

输入的第一行包含一个整数 TT,表示询问的个数。

接下来 TT 行,每行包含一组询问,其中第 ii 行包含两个整数lil_irir_i ,表示询问数列中第 lil_i 个数到第 rir_i个数的和。

Output

输出 T 行,每行包含一个整数表示对应询问的答案

Samples

3
1 1
1 3
5 8
1
4
8

Limitation

1s, 1024KiB for each test case.

对于 10% 的评测用例,1T30,1liri1001 ≤ T ≤ 30, 1 ≤ l_i ≤ r_i ≤ 100

对于 20% 的评测用例,1T100,1liri10001 ≤ T ≤ 100, 1≤ l_i ≤ r_i ≤ 1000

对于 40% 的评测用例,1T1000,1liri1061 ≤ T ≤ 1000, 1 ≤ l_i ≤ r_i ≤ 10^6

对于 70% 的评测用例,1T10000,1liri1091 ≤ T ≤ 10000, 1 ≤ l_i ≤ r_i ≤ 10^9

对于 80% 的评测用例,1T1000,1liri10121 ≤ T ≤ 1000, 1 ≤ l_i ≤ r_i ≤ 10^{12}

对于 90% 的评测用例,1T10000,1liri10121 ≤ T ≤ 10000, 1 ≤ l_i ≤ r_i ≤ 10^{12}

对于所有评测用例,1T100000,1liri10121 ≤ T ≤ 100000, 1≤ l_i ≤ r_i ≤ 10^{12}