CF249E.Endless Matrix

俄罗斯的太空旅行者 Alisa Selezneva，和 21 世纪末的其他女学生一样，对科学充满兴趣。最近她参观了 MIT（莫斯科时间研究院），那里的主席、时光机的共同发明者 Petrov 院士向她讲解了时光机的结构。

在时光机演示期间，Alisa 注意到机器的速度并不高，于是对这一缺点产生了兴趣。经过仔细研究后发现，时光机中有一个问题并未被最优地解决。如果你能找到最优解法，时光机将运行更快且消耗更少能量。

这个所有员工都无法最优解决的问题如下。存在一个矩阵 $a$，它按照如下规则填充：

矩阵中的单元格依次填入正整数，起始于 1。对于 $a_{i,j}$ 和 $a_{t,k}$（$i,j,t,k \geq 1$），若满足下列条件，则有 $a_{i,j}<a_{t,k}$：

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$ 如下所示：

为了解决这个问题，你需要快速求出给定 $x_{1},y_{1},x_{2},y_{2}$（$x_{1} \leq x_{2},y_{1} \leq y_{2}$）时，表达式

的值。

由于该表达式的结果可能非常大，只需要输出其最后 10 位数字即可。

因此，在 MTI 里没有人能解决本题。Alisa 勇敢地决定用时光机穿越到过去来寻求你的帮助。

你的任务是编写一个程序，根据给定的 $x_{1}, y_{1}, x_{2}, y_{2}$，求出该表达式最后 $10$ 位数字。

第一行包含一个整数 $t$（$1 \leq t \leq 10^{5}$），表示需要解决的测试用例数量。

接下来的每一行，描述一个测试用例，包括四个正整数 $x_{1}, y_{1}, x_{2}, y_{2}$（$1 \leq x_{1} \leq x_{2} \leq 10^{9}, 1 \leq y_{1} \leq y_{2} \leq 10^{9}$），它们由空格分隔。

对于每个询问，若表达式的值不超过 $10$ 位字符，则输出该值。否则输出三个字符“.”，以及该数值后 $10$ 位。每个答案占一行。请严格按照样例格式输出。

由 ChatGPT 5 翻译