俄罗斯太空旅行者 Alisa Selezneva 和 21 世纪末的其他女学生一样,对科学感兴趣。她最近访问了麻省理工学院(莫斯科时间研究所),该研究所的主席、时间机器的共同发明人彼得罗夫院士向她讲述了时间机器的建造过程。
在演示时间机器性能时,Alisa 注意到机器速度不高,女孩对这种缺点的原因很感兴趣。经过仔细检查发现,时间机器应该解决的问题之一并不是通过最佳算法来解决的。如果你找到一种最佳方法来解决这个问题,时间机器就会运行得更快并且消耗更少的能量。
没有一个员工能够最佳解决的任务如下。存在一个矩阵a,其填充规则如下:
单元格是从 1 开始的连续正整数。另外,ai,j < at,k(i,j,t,k≥1),若:
1. max(i, j) < max(t, k);
2. max(i, j) = max(t, k)且j < k;
3. max(i, j) = max(t, k),j = k 且 i > t。
因此,插入前 36 个数字后,矩阵 a 将如下所示:
要解决这个问题,你应该学会快速找到给定的 x1、y1、x2 和 y2 值(x1 ≤ x2,y1 ≤ y2)表达式的含义:
$$\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} a_{i,j}$$
由于该表达式的含义可能足够大,因此只需知道所查找值的最后 10 位数字就足够了。
因此,MTI 中没有人能够解决给定的任务。爱丽丝勇敢地使用时间机器穿越过去来帮助你。
您的任务是编写一个程序,使用给定值 x1、y1、x2 和 y2 查找给定表达式的最后 10 位数字。
输入
第一个输入行包含一个整数 t (1 ≤ t ≤ 105) — 您应该解决问题的测试集的数量。
接下来的 t 行中的每一行都包含测试的描述 - 四个正整数 x1、y1、x2 和 y2 (1 ≤ x1 ≤ x2 ≤ 109, 1 ≤ y1 ≤ y2 ≤ 109),用空格分隔。
输出
对于每个查询,如果表达式最多包含 10 个字符,则打印表达式的含义。 Otherwise, print three characters "." (不带引号),然后是时间表达式的最后十位数字。 Print the answer to each query on a single line.尽可能遵循示例中给出的格式。
示例
输入 #1
5 1 1 1 1 2 2 3 3 2 3 5 6 100 87 288 2002 4 2 5 4
输出 #1
1 24 300 ...5679392764 111