Dqs的遗产

题号：NC21793
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

dqs想在退役的时候，把他用来学习打的书送给新生。深思熟虑之后，dqs决定出一道水题，只要能过了这道题，就有机会获得他的遗产。
dqs找了一个无限大的矩阵，记矩阵的第i行第j列的元素为 ${}a_{i,j}$ ，则 ${}a_{i,j}= i*j$ 。举例来说，矩阵的前5行的前5列为
$\left[\begin{array}{cccc} 1 &2 &3 &4 &5\\ 2 &4& 6 &8 &10\\ 3& 6& 9 &12& 15\\ 4 &8 &12& 16 &20\\ 5 &10 &15 &20& 25 \end{array}\right]$
但是dqs是个白学家，所以他特别喜欢三角形。为了把矩阵也变成三角形，他把矩阵中的第i列全部往下移了行，记新的矩阵中第i行第j列的元素为 ${}b_{i,j}$ ，则 ${}a_{i,j} = b_{i,j+i-1}$ 。也就是说现在的矩阵前5行前5列为
$\left[\begin{array}{cccc} 1\\ 2 &2\\ 3 &4 &3\\ 4 &6 &6 &4\\ 5 &8 &9 &8 &5 \end{array}\right]$
dqs想知道由 ${}b_{Xmin,Ymin}, b_{Xmin,Ymax}, b_{Xmax,Ymin}, b_{Xmax,Ymax}$ 四个点围成的矩形中所有元素的和是多少，其中代表第行第列的元素。由于答案很大，因此只需要输出对取模后的结果

输入描述:

第一行输入T，代表样例个数，接下来T行每行由4个整数组成，分别代表。
其中:

输出描述:

输出T行，每行一个整数，代表矩形中所有元素的和。

示例1

输入

复制

输出

复制