Mikasa always wants to protect Eren at any cost. Even when Eren transforms into his “Attack Titan” form. The country where Mikasa and Eren live is surrounded by a rectangular wall named “Wall Maria” of size A × B where A is the length and B is the width of the wall. There’s another rectangular wall within Wall Maria named “Wall Sina” of size C×D where C is the length and D is the width of the wall. Mikasa knows Eren is fighting with some mindless Titans somewhere between Wall Maria and Wall Sina.

Now, Mikasa wants to reach Eren and fight alongside him. But, She doesn’t know how much area she has to search in order to find Eren. Since, Mikasa has only one talent which is killing Titans mercilessly, She needs your help to find the total area between Wall Maria and Wall Sina. Help her to find Eren.

Input

Input starts with an integer T (≤ 100000), denoting the number of test cases. Each of the next T lines contains 4 integers A, B, C, D (1 <= A, B, C, D <= 10^18, C <= A, D <= B) indicating the length and width of the outer Wall, the length and width of the inner Wall.

Output

For each case print the area which lies between Wall Maria and Wall Sina. Since the answer could be very big, print it modulo 1000000007.

Sample

Input:
6
4 5 2 3
10 20 2 4
10 20 10 20
7 8 7 7
2 2 1 1
1000000000000000000 1000000000000000000 1 1
Output:
14
192
0
7
3
2400