A13813 | 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'| > 0$ , $|b - b'| > 0$ , and $|a - a'| + |b - b'| = 3$ . Of course, the knight cannot leave the chessboard.

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)$ .

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