Background

2021年蓝桥杯国赛F题

Description

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

小蓝发现，这个数列前 $1$ 项是整数 $1$，接下来 $2$ 项是整数 $1$ 至 $2$，接下来

$3$ 项是整数 $1$ 至 $3$，接下来 $4$ 项是整数 $1$ 至 $4$，依次类推。

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

Format

Input

输入的第一行包含一个整数 $T$，表示询问的个数。

接下来 $T$ 行，每行包含一组询问，其中第 $i$行包含两个整数$l_i$和 $r_i$ ，表示询问数列中第 $l_i$ 个数到第 $r_i$个数的和。

Output

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

Samples

3
1 1
1 3
5 8

1
4
8

Limitation

1s, 1024KiB for each test case.

对于 10% 的评测用例，$1 ≤ T ≤ 30, 1 ≤ l_i ≤ r_i ≤ 100$。

对于 20% 的评测用例，$1 ≤ T ≤ 100, 1≤ l_i ≤ r_i ≤ 1000$。

对于 40% 的评测用例，$1 ≤ T ≤ 1000, 1 ≤ l_i ≤ r_i ≤ 10^6$。

对于 70% 的评测用例，$1 ≤ T ≤ 10000, 1 ≤ l_i ≤ r_i ≤ 10^9$。

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

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

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