前缀和是指将一个序列中每个位置前面所有元素的和预处理出来，以便于后续查询。这个技巧在一些区间求和问题中非常有用，比如统计数组中某一段区间内的元素和。时间复杂度为O(n)。

二分查找是一种高效的查找算法，在已排序的数组中查找特定值的位置。它的时间复杂度是O(log n)。这个算法的基本思想是将待查找区间不断缩小，直到找到目标值。

题目描述

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

1,1,2,1,2,3,1,2,3,4,⋯1,1,2,1,2,3,1,2,3,4,⋯

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

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

输入描述

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

接下来 TT 行，每行包含一组询问，其中第 ii 行包含两个整数 lili​ 和 riri​，表示询问数列中第 lili​ 个数到第 riri​ 个数的和。

输出描述

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

输入输出样例

示例

输入

3
1 1
1 3
5 8

输出

1
4
8

评测用例规模与约定

对于 1010% 的评测用例，1≤T≤30,1≤li≤ri≤1001≤T≤30,1≤li​≤ri​≤100。

对于 2020% 的评测用例，1≤T≤100,1≤li≤ri≤10001≤T≤100,1≤li​≤ri​≤1000。

对于 4040% 的评测用例，1≤T≤1000,1≤li≤ri≤1061≤T≤1000,1≤li​≤ri​≤106。

对于 7070% 的评测用例，1≤T≤10000,1≤li≤ri≤1091≤T≤10000,1≤li​≤ri​≤109。

对于 8080% 的评测用例，1≤T≤1000,1≤li≤ri≤10121≤T≤1000,1≤li​≤ri​≤1012。

对于 9090% 的评测用例，1≤T≤10000,1≤li≤ri≤10121≤T≤10000,1≤li​≤ri​≤1012。

对于所有评测用例，1≤T≤100000,1≤li≤ri≤10121≤T≤100000,1≤li​≤ri​≤1012。

运行限制

• 最大运行时间：5s
• 最大运行内存: 256M

import java.util.*;
//通过了百分之八十的用例，其余超时
public class erfen {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();long[][] a=new long[n][2];for(int i=0;i