Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Attack Titan

By raihan.raka · Limits 1s, 512 MB

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

InputOutput
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
14
192
0
7
3
2400

    Discussion

    Statistics


    68% Solution Ratio

    saiful_alamEarliest, Oct '20

    prodip_bsmrstuFastest, 0.0s

    saiful_alamLightest, 1.0 MB

    ADRI0777Shortest, 119B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.