Captain of Knights SOLUTION
Mr. Chanek just won the national chess tournament and got a huge chessboard of size N×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)=∑Ni=X∑Mj=YF(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.
Input
The first line contains an integer T (1≤T≤100), the number of test cases.
Each test case contains a line with four integers X Y N M (3≤X≤N≤109,3≤Y≤M≤109).
Output
For each test case, print a line with the value of G(X,Y) modulo 109+7.
Example
input
2
3 4 5 6
5 5 8 8
output
27
70
