A. A Times B
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Boxlunch is on a map which can be modeled as an infinite grid of cells, with cell $$$(i,j)$$$ having value $$$i \times j$$$. Boxlunch starts at cell $$$(a,b)$$$ and is trying to reach cell $$$(n,m)$$$, where $$$n \ge a$$$ and $$$m \ge b$$$.

If Boxlunch is at cell $$$(x,y)$$$, he can either move to cell $$$(x+1, y)$$$ or $$$(x, y+1)$$$.

The total value of his path is the sum of the values of all cells he visits, including his starting and ending cells.

Find the maximum total value of a path he can take to reach cell $$$(n,m)$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.

The only line of each test contains four integers $$$a$$$, $$$b$$$, $$$n$$$, and $$$m$$$ — Boxlunch's starting location and his target location $$$(0 \le a,b \le 10^6, a \le n \le 10^6, b \le m \le 10^6)$$$.

It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$10^6$$$, and that the sum of the values of $$$m$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single number — the maximum total value over all paths Boxlunch can take to reach cell $$$(n, m)$$$.

Example
Input
6
1 1 3 1
1 1 2 4
1 1 1 1
1 3 4 3
1 4 3 4
3 900000 900000 900000
Output
6
21
1
30
24
364500404997300000
Note

In the first test case, the only path Boxlunch can take is moving to cell $$$(2,1)$$$, then to cell $$$(3,1)$$$, giving a value of $$$1 \times 1 + 2 \times 1 + 3 \times 1 = 1 + 2 + 3 = 6$$$.

In the second test case, the following image shows the optimal path Boxlunch could take, giving a value of $$$1+2+4+6+8 = 21$$$.

In the third test case, Boxlunch doesn't have to move, giving a value of $$$1\times 1 = 1$$$.

In the last test, note that the answer may not fit in a $$$32$$$-bit integer.