human
Can you provide a Python program to print the number of possible different sums on the way from the start cell to the end cell given the following:
During the quarantine, Sicromoft has more free time to create the new functions in "Celex-2021". The developers made a new function GAZ-GIZ, which infinitely fills an infinite table to the right and down from the upper left corner as follows:

 The cell with coordinates (x, y) is at the intersection of x-th row and y-th column. Upper left cell (1,1) contains an integer 1.

The developers of the SUM function don't sleep either. Because of the boredom, they teamed up with the developers of the RAND function, so they added the ability to calculate the sum on an arbitrary path from one cell to another, moving down or right. Formally, from the cell (x,y) in one step you can move to the cell (x+1, y) or (x, y+1). 

After another Dinwows update, Levian started to study "Celex-2021" (because he wants to be an accountant!). After filling in the table with the GAZ-GIZ function, he asked you to calculate the quantity of possible different amounts on the path from a given cell (x_1, y_1) to another given cell (x_2, y_2), if you can only move one cell down or right.

Formally, consider all the paths from the cell (x_1, y_1) to cell (x_2, y_2) such that each next cell in the path is located either to the down or to the right of the previous one. Calculate the number of different sums of elements for all such paths.

Input

The first line contains one integer t (1 ≤ t ≤ 57179) — the number of test cases.

Each of the following t lines contains four natural numbers x_1, y_1, x_2, y_2 (1 ≤ x_1 ≤ x_2 ≤ 10^9, 1 ≤ y_1 ≤ y_2 ≤ 10^9) — coordinates of the start and the end cells. 

Output

For each test case, in a separate line, print the number of possible different sums on the way from the start cell to the end cell.

Example

Input

4
1 1 2 2
1 2 2 4
179 1 179 100000
5 7 5 7

Output

2
3
1
1

Note

In the first test case there are two possible sums: 1+2+5=8 and 1+3+5=9. 
Solve the task in PYTHON.
assistant
#Here is Python program to print the number of possible different sums on the way from the start cell to the end cell.

"""
    Satwik_Tiwari ;) .
    4th july , 2020  - Saturday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
       ...