Background

小蓝发现了一个有趣的数列，这个数列的前几项如下：

1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …

小蓝发现，这个数列前 11项是整数 1，接下来 2 项是整数 1 至 2，接下来 3 项是整数 1 至 3，接下来 4项是整数 1 至 4，依次类推。

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

Format

Input

输入的第一行包含一个整数T，表示询问的个数。 接下来的T行，每行包含一组询问，其中第i行包括两个整数li和ri，表示询问li到ri的数的和。

Output

输出t行对应的答案。

Samples

3
1 1
1 3
5 8

1
4
8

Limitation

对于 $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$ 。