CF1425C.Captain of Knights

Mr. Chanek just won the national chess tournament and got a huge chessboard of size $N \times M$. Bored with playing conventional chess, Mr. Chanek now defines a function $F(X, Y)$, which denotes the minimum number of moves to move a knight from square $(1, 1)$ to square $(X, Y)$. It turns out finding $F(X, Y)$ is too simple, so Mr. Chanek defines:

$G(X, Y) = \sum_{i=X}^{N} \sum_{j=Y}^{M} F(i, j)$

Given X and Y, you are tasked to find $G(X, Y)$.

A knight can move from square $(a, b)$ to square $(a', b')$ if and only if $|a - a'| \gt 0$, $|b - b'| \gt 0$, and $|a - a'| + |b - b'| = 3$. Of course, the knight cannot leave the chessboard.

陈先生刚刚赢得了全国国际象棋锦标赛，并获得了一个大小为 $N \times M$ 的巨型棋盘。厌倦了传统国际象棋的玩法，陈先生定义了一个函数 $F(X, Y)$，表示马从格子 $(1, 1)$ 移动到格子 $(X, Y)$ 所需的最少步数。结果发现计算 $F(X, Y)$ 过于简单，因此陈先生进一步定义：

$$G(X, Y) = \sum_{i=X}^{N} \sum_{j=Y}^{M} F(i, j)$$

给定 $X$ 和 $Y$，你需要计算 $G(X, Y)$。

马可以从格子 $(a, b)$ 移动到格子 $(a', b')$ 当且仅当 $|a - a'| \gt 0$，$|b - b'| \gt 0$，且 $|a - a'| + |b - b'| = 3$。当然，马不能移出棋盘边界。

The first line contains an integer $T$ $(1 \le T \le 100)$, the number of test cases.

Each test case contains a line with four integers $X$ $Y$ $N$ $M$ $(3 \leq X \leq N \leq 10^9, 3 \leq Y \leq M \leq 10^9)$.

第一行包含一个整数 $T$ $(1 \le T \le 100)$，表示测试用例的数量。

每个测试用例包含一行，包含四个整数 $X$ $Y$ $N$ $M$ $(3 \leq X \leq N \leq 10^9, 3 \leq Y \leq M \leq 10^9)$。

For each test case, print a line with the value of $G(X, Y)$ modulo $10^9 + 7$.

对于每个测试用例，输出一行，表示 $G(X, Y)$ 对 $10^9 + 7$ 取模的值。