题目描述

一座古堡大厅的地面是一张无限大的正方形网格。克拉基尔猫想按照自己设计的“螺旋式”规则，从 $1$ 开始用连续正整数给所有格子编号。

格子位置用 $(i,j)$ 表示，其中 $i$ 为行号，$j$ 为列号，均从 $1$ 开始。

记格子 $(i,j)$ 中的编号为 $a_{i,j}$。对于任意正整数 $i,j,k,l$，当满足下列任意一条时，有 $a_{i,j}<a_{k,l}$：

1. $\max(i,j)<\max(k,l)$；
2. $\max(i,j)=\max(k,l)$ 且 $i<k$；
3. $\max(i,j)=\max(k,l)$、$i=k$ 且 $j>l$。

也就是说，编号按一层一层的方式进行。每增加一层，先沿新的一列从上向下编号，然后沿新的一行从右向左编号。

前 $6\times6$ 个格子的编号如下：

Gargamel 需要快速求出许多矩形区域内所有格子编号之和。对于给定的 $x_1,x_2,y_1,y_2$，其中 $x_1\le x_2$、$y_1\le y_2$，需要计算：

$\displaystyle \sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}a_{i,j}$。

答案可能非常巨大，因此使用以下输出格式：

• 若答案不超过 $10$ 位十进制数字，则完整输出；
• 否则输出三个点 ...，再紧接答案的最后 10 位数字；
• 如果最后 $10$ 位中存在前导零，也必须保留，使三个点之后始终恰好有 $10$ 个数字。

输入格式

第一行包含一个整数 $q$，表示询问数：

$1\le q\le10^5$。

接下来 $q$ 行，每行包含四个正整数 $x_1,y_1,x_2,y_2$：

$1\le x_1\le x_2\le10^9$，

$1\le y_1\le y_2\le10^9$。

输出格式

对于每个询问输出一行答案，格式按照题目描述中的规则。

样例

5
1 1 2 2
2 3 3 4
4 2 5 4
6 7 6 7
500 670 766 992

10
36
111
42
...0434052467

样例说明

• 第一个询问的和为 $1+2+4+3=10$；
• 第二个询问的和为 $6+11+7+12=36$。

子任务