Read problems statements in Mandarin Chinese and Russian as well. 
Your friend Сhef has prepared a rectangular cake for you. Both of you want to divide the cake among yourselves. Your friend is generous enough to let you choose your share first. You have decided to take two pieces.

For the first piece you make a rectangular cut (each side of this cut is parallel to the corresponding side of the cake) inside the cake. Now the cake have two pieces. You take the piece inside the rectangle cut. For the second piece, you make another rectangular cut (each side of this cut is parallel to the corresponding side of the cake) inside the cake. Now the cake again have two pieces. You take the piece inside the rectangle cut (note that this piece may not be rectangular, because of cut may cross an empty space that remains from the first piece, also it can be empty). Your friend will have the rest of the cake.

Given the cuts determine the amount of cake that you will have. The amount is calculated as the sum of the areas covered by your pieces. The cake can be considered as a rectangle with the lower left corner at (0,0) and the upper right corner at (1001,1001).

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of two lines. Each line contains the description of a rectangular cut by giving the information of the rectangle. A rectangle is defined by four integers (co-ordinate of the lower-left corner (x1,y1) and upper right corner (x2,y2)). 

------ Output ------ 

For each test case, output a single line containing the amount of cake you will have. 

------ Constraints ------ 

$1≤T≤100$
$1≤x1x2≤1000$
$1≤y1y2≤1000$

----- Sample Input 1 ------ 
2
1 1 10 10
11 11 20 20
1 1 20 20
11 11 30 30
----- Sample Output 1 ------ 
162
641
----- explanation 1 ------ 
Test Case 1:
The area of the first piece is 81 and the area of the second piece is 81, a total of 162. 

Test Case 2:
The area of the first piece is 361 and the area of the second piece is 280, a total of 641.

Difficulty: MEDIUM
Tags: Geometry

Starter code:

Solutions:
t = int(input())
for i in range(t):
	x = [int(x) for x in input().split()]
	y = [int(x) for x in input().split()]
	a1 = (x[2] - x[0]) * (x[3] - x[1])
	a2 = (y[2] - y[0]) * (y[3] - y[1])
	a = 0
	xd = min(x[2], y[2]) - max(x[0], y[0])
	yd = min(x[3], y[3]) - max(x[1], y[1])
	if xd > 0 and yd > 0:
		a = xd * yd
	print(a1 + a2 - a)


try:
	t = int(input())
	while t > 0:
		(x1, y1, x2, y2) = [int(i) for i in input().split()]
		(x3, y3, x4, y4) = [int(i) for i in input().split()]
		bottomX = max(x1, x3)
		bottomY = max(y1, y3)
		upperX = min(x2, x4)
		upperY = min(y2, y4)
		subtract = 0
		if bottomX < upperX and bottomY < upperY:
			subtract = (upperX - bottomX) * (upperY - bottomY)
		print((x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3) - subtract)
		t = t - 1
except:
	pass


t = int(input())
for tc in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	(x3, y3, x4, y4) = map(int, input().split())
	bottomX = max(x1, x3)
	bottomY = max(y1, y3)
	upperX = min(x2, x4)
	upperY = min(y2, y4)
	subtract = 0
	if bottomX < upperX and bottomY < upperY:
		subtract = (upperX - bottomX) * (upperY - bottomY)
	print((x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3) - subtract)


for _ in range(int(input())):
	(x1, y1, x2, y2) = [int(i) for i in input().split()]
	(x3, y3, x4, y4) = [int(i) for i in input().split()]
	bottomX = max(x1, x3)
	bottomY = max(y1, y3)
	upperX = min(x2, x4)
	upperY = min(y2, y4)
	subtract = 0
	if bottomX < upperX and bottomY < upperY:
		subtract = (upperX - bottomX) * (upperY - bottomY)
	print((x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3) - subtract)


for x in range(int(input())):
	(x1_1, y1_1, x1_2, y1_2) = map(int, input().split())
	(x2_1, y2_1, x2_2, y2_2) = map(int, input().split())
	common_area = 0
	if x2_1 < x1_2 and x2_2 > x1_1:
		if y2_1 < y1_2 and y2_2 > y1_1:
			common_area = 1
	print((x1_2 - x1_1) * (y1_2 - y1_1) + (x2_2 - x2_1) * (y2_2 - y2_1) - common_area * ((min(x1_2, x2_2) - max(x1_1, x2_1)) * (min(y1_2, y2_2) - max(y1_1, y2_1))))


for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	(X1, Y1, X2, Y2) = map(int, input().split())
	area1 = (x2 - x1) * (y2 - y1)
	area2 = (X2 - X1) * (Y2 - Y1)
	area3 = 0
	b1 = max(x1, X1)
	b2 = max(y1, Y1)
	b3 = min(x2, X2)
	b4 = min(y2, Y2)
	if b1 < b3 and b2 < b4:
		area3 = (b3 - b1) * (b4 - b2)
	print(area1 + area2 - area3)


for i in range(int(input())):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	(x3, y3, x4, y4) = list(map(int, input().split()))
	a = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3)
	b1 = max(x1, x3)
	b2 = max(y1, y3)
	b3 = min(x2, x4)
	b4 = min(y2, y4)
	if b1 < b3 and b2 < b4:
		a = a - (b3 - b1) * (b4 - b2)
	print(a)


def area(A):
	return (A[2] - A[0]) * (A[3] - A[1])
test = int(input())
for _ in range(test):
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	ans = area(A) + area(B)
	(left, bottom, right, top) = (max(A[0], B[0]), max(A[1], B[1]), min(A[2], B[2]), min(A[3], B[3]))
	if right > left and top > bottom:
		ans -= area([left, bottom, right, top])
	print(ans)


def getAns(R):
	if R[2] < R[0] or R[3] < R[1]:
		return 0
	return (R[2] - R[0]) * (R[3] - R[1])
for tc in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	R1 = (x1, y1, x2, y2)
	(x1, y1, x2, y2) = map(int, input().split())
	R2 = (x1, y1, x2, y2)
	ans = getAns(R1)
	ans += getAns(R2)
	ans -= getAns((max(R1[0], R2[0]), max(R1[1], R2[1]), min(R1[2], R2[2]), min(R1[3], R2[3])))
	print(ans)


for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	(x3, y3, x4, y4) = map(int, input().split())
	p = 0
	x5 = max(x1, x3)
	y5 = max(y1, y3)
	x6 = min(x2, x4)
	y6 = min(y2, y4)
	p = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3)
	if x5 < x6 and y5 < y6:
		p -= (x6 - x5) * (y6 - y5)
	print(p)


t = int(input())
for _ in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	(x3, y3, x4, y4) = map(int, input().split())
	a = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3)
	xlim1 = max(x1, x3)
	xlim2 = min(x2, x4)
	ylim1 = max(y1, y3)
	ylim2 = min(y2, y4)
	if xlim1 < xlim2 and ylim1 < ylim2:
		a -= (xlim2 - xlim1) * (ylim2 - ylim1)
	print(a)


for _ in range(int(input())):
	(a1, b1, a2, b2) = map(int, input().split())
	(x1, y1, x2, y2) = map(int, input().split())
	ans = (a2 - a1) * (b2 - b1)
	ans += (x2 - x1) * (y2 - y1)
	bottomX = max(a1, x1)
	bottomY = max(b1, y1)
	upperX = min(a2, x2)
	upperY = min(b2, y2)
	if bottomX < upperX and bottomY < upperY:
		ans -= (upperX - bottomX) * (upperY - bottomY)
	print(ans)


for _ in range(int(input())):
	(a1, b1, c1, d1) = map(int, input().split())
	(a2, b2, c2, d2) = map(int, input().split())
	res = (c1 - a1) * (d1 - b1) + (c2 - a2) * (d2 - b2)
	(l, m, n, o) = (max(a1, a2), max(b1, b2), min(c1, c2), min(d1, d2))
	if l < n and m < o:
		res -= (n - l) * (o - m)
	print(res)


t = int(input())
while t > 0:
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	res = (l1[2] - l1[0]) * (l1[3] - l1[1]) + (l2[2] - l2[0]) * (l2[3] - l2[1])
	l = max(l1[0], l2[0])
	m = max(l1[1], l2[1])
	o = min(l1[2], l2[2])
	p = min(l1[3], l2[3])
	if l < o and m < p:
		res = res - (o - l) * (p - m)
	print(res)
	t -= 1


for _ in range(int(input())):
	(x1, y1, x2, y2) = [int(x) for x in input().split()]
	(x3, y3, x4, y4) = [int(x) for x in input().split()]
	ans = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3)
	if x4 <= x1 or x3 >= x2 or y4 <= y1 or (y3 >= y2):
		print(ans)
	else:
		x = [x1, x2, x3, x4]
		x.sort()
		lx = x[2] - x[1]
		y = [y1, y2, y3, y4]
		y.sort()
		ly = y[2] - y[1]
		ans -= lx * ly
		print(ans)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	(e, f, g, h) = map(int, input().split())
	x = (c - a) * (d - b)
	y = (g - e) * (h - f)
	z = 0
	p = max(a, e)
	q = max(b, f)
	r = min(c, g)
	s = min(d, h)
	if p < r and q < s:
		z = (r - p) * (s - q)
	print(x + y - z)


t = int(input())
for it in range(t):
	(x1, y1, x2, y2) = [int(word) for word in input().split()]
	(x3, y3, x4, y4) = [int(word) for word in input().split()]
	disjoint = x2 <= x3 or x4 <= x1 or y2 <= y3 or (y4 <= y1)
	area1 = (x2 - x1) * (y2 - y1)
	area2 = (x4 - x3) * (y4 - y3)
	areac = 0
	if not disjoint:
		(xm1, xm2) = sorted([x1, x2, x3, x4])[1:3]
		(ym1, ym2) = sorted([y1, y2, y3, y4])[1:3]
		areac = (xm2 - xm1) * (ym2 - ym1)
	print(area1 + area2 - areac)


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)
	return r1 if r1 == r2 else None

def alg(r1, r2):
	x1 = 0
	y1 = 1
	x2 = 2
	y2 = 3
	area1 = (r1[x2] - r1[x1]) * (r1[y2] - r1[y1])
	collx1 = max(r1[x1], r2[x1])
	colly1 = max(r1[y1], r2[y1])
	collx2 = min(r1[x2], r2[x2])
	colly2 = min(r1[y2], r2[y2])
	area2 = (r2[x2] - r2[x1]) * (r2[y2] - r2[y1])
	if collx2 > collx1 and colly2 > colly1:
		areacoll = (collx2 - collx1) * (colly2 - colly1)
	else:
		areacoll = 0
	return area1 + area2 - areacoll

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		r1 = list(map(int, data.readline().split()))
		r2 = list(map(int, data.readline().split()))
		res = alg(r1, r2)
		print(res)
main()


tests = int(input())
for i in range(tests):
	(x1, y1, x2, y2) = map(int, input().split())
	(x3, y3, x4, y4) = map(int, input().split())
	ans = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3)
	x_diff = 0
	y_diff = 0
	if x1 <= x3 < x2 <= x4:
		x_diff = x2 - x3
	elif x1 <= x3 < x4 <= x2:
		x_diff = x4 - x3
	elif x3 <= x1 < x4 <= x2:
		x_diff = x4 - x1
	elif x3 <= x1 < x2 <= x4:
		x_diff = x2 - x1
	if y1 <= y3 < y2 <= y4:
		y_diff = y2 - y3
	elif y1 <= y3 < y4 <= y2:
		y_diff = y4 - y3
	elif y3 <= y1 < y4 <= y2:
		y_diff = y4 - y1
	elif y3 <= y1 < y2 <= y4:
		y_diff = y2 - y1
	remove = x_diff * y_diff
	print(ans - remove)


for i in range(int(input())):
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	res = (l1[2] - l1[0]) * (l1[3] - l1[1]) + (l2[2] - l2[0]) * (l2[3] - l2[1])
	l = max(l1[0], l2[0])
	m = max(l1[1], l2[1])
	o = min(l1[2], l2[2])
	p = min(l1[3], l2[3])
	if l < o and m < p:
		res = res - (o - l) * (p - m)
	print(res)


t = int(input())
for dummy in range(t):
	s = input()
	s = s.split(' ')
	y = input()
	y = y.split(' ')
	if s[0] > y[0]:
		z = s
		s = y
		y = z
	for i in range(4):
		s[i] = int(s[i])
		y[i] = int(y[i])

	def q(s, y):
		if min(s[3], y[3]) > max(s[1], y[1]) and min(s[2], y[2]) > max(s[0], y[0]):
			return (min(s[3], y[3]) - max(s[1], y[1])) * (min(s[2], y[2]) - max(s[0], y[0]))
		return 0
	print((s[2] - s[0]) * (s[3] - s[1]) + (y[2] - y[0]) * (y[3] - y[1]) - q(s, y))


T = int(input())
for case in range(T):
	(x1, y1, x2, y2) = [int(i) for i in input().split()]
	(x3, y3, x4, y4) = [int(i) for i in input().split()]
	rect1Area = (x2 - x1) * (y2 - y1)
	rect2Area = (x4 - x3) * (y4 - y3)
	x5 = max(x1, x3)
	y5 = max(y1, y3)
	x6 = min(x2, x4)
	y6 = min(y2, y4)
	totalArea = rect1Area + rect2Area
	if x5 < x6 and y5 < y6:
		totalArea -= (x6 - x5) * (y6 - y5)
	print(totalArea)


T = int(input())
for t in range(T):
	(x1, y1, x2, y2) = map(int, input().split())
	(a1, b1, a2, b2) = map(int, input().split())
	h = 0
	if x2 >= a2 and x1 <= a1:
		h = a2 - a1
	elif a2 >= x2 and a1 <= x1:
		h = x2 - x1
	elif a1 >= x2 or x1 >= a2:
		h = 0
	elif x2 >= a1 and x2 <= a2:
		h = x2 - a1
	else:
		h = a2 - x1
	v = 0
	if y2 >= b2 and y1 <= b1:
		v = b2 - b1
	elif b2 >= y2 and b1 <= y1:
		v = y2 - y1
	elif b1 >= y2 or y1 >= b2:
		v = 0
	elif y2 >= b1 and y2 <= b2:
		v = y2 - b1
	else:
		v = b2 - y1
	print((x2 - x1) * (y2 - y1) + (a2 - a1) * (b2 - b1) - h * v)


T = int(input())
for i in range(T):
	(x1, y1, x2, y2) = map(int, input().split())
	(x3, y3, x4, y4) = map(int, input().split())
	area1 = (x2 - x1) * (y2 - y1)
	area2 = (x4 - x3) * (y4 - y3)
	x5 = max(x3, x1)
	y5 = max(y3, y1)
	x6 = min(x2, x4)
	y6 = min(y2, y4)
	if x5 > x6 or y5 > y6:
		print(area1 + area2)
	else:
		print(area1 + area2 - (x6 - x5) * (y6 - y5))


for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	(a1, b1, a2, b2) = map(int, input().split())
	r1 = (x2 - x1) * (y2 - y1)
	r2 = (a2 - a1) * (b2 - b1)
	x = [x1, x2, a1, a2]
	y = [y1, y2, b1, b2]
	x.sort()
	y.sort()
	com = 0
	if abs((x1 + x2) / 2 - (a1 + a2) / 2) < (x2 - x1 + a2 - a1) / 2 and abs((y1 + y2) / 2 - (b1 + b2) / 2) < (y2 - y1 + b2 - b1) / 2:
		com = (x[2] - x[1]) * (y[2] - y[1])
	print(int(r1 + r2 - com))


case = int(input())
n = 1002
for i in range(case):
	area = 0
	(x1, y1, x2, y2) = map(int, input().split(' '))
	length = x2 - x1
	breath = y2 - y1
	area += length * breath
	(m1, n1, m2, n2) = map(int, input().split(' '))
	length = m2 - m1
	breath = n2 - n1
	area += length * breath
	if m1 > x2 or n1 > y2 or x1 > m2 or (y1 > n2):
		print(area)
		continue
	l = min(x2, m2) - max(x1, m1)
	b = min(y2, n2) - max(y1, n1)
	area -= l * b
	print(area)


for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	(x3, y3, x4, y4) = map(int, input().split())
	d = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3)
	b1 = max(x1, x3)
	b2 = max(y1, y3)
	b3 = min(x2, x4)
	b4 = min(y2, y4)
	if b1 < b3 and b2 < b4:
		d -= (b3 - b1) * (b4 - b2)
	print(d)


x1 = 0
y1 = 1
x2 = 2
y2 = 3
tests = int(input())
for test in range(tests):
	r1 = list(map(int, input().split()))
	r2 = list(map(int, input().split()))
	area = (r1[x2] - r1[x1]) * (r1[y2] - r1[y1]) + (r2[x2] - r2[x1]) * (r2[y2] - r2[y1])
	x = min(r1[x2], r2[x2]) - max(r1[x1], r2[x1])
	y = min(r1[y2], r2[y2]) - max(r1[y1], r2[y1])
	if x > 0 and y > 0:
		area -= x * y
	print(area)


T = int(input())
while T > 0:
	(a, b, c, d) = map(int, input().split())
	(e, f, g, h) = map(int, input().split())
	c_x = min((g, c)) - max((a, e))
	c_y = min((d, h)) - max((b, f))
	c_a = 0
	if c_x >= 0 and c_y >= 0:
		c_a = c_x * c_y
	print((c - a) * (d - b) + (g - e) * (h - f) - c_a)
	T -= 1


def trange():
	return range(int(input()))

def splitMap():
	return map(int, input().split())

def listOfNumbers():
	return list(map(int, input().split()))

def number():
	return int(input())

def binary(x):
	return bin(x).replace('0b', '')
import math
from collections import Counter
import functools

def doOverlap(rect1, rect2):
	return rect1[0] < rect2[2] and rect1[2] > rect2[0] and (rect1[1] < rect2[3]) and (rect1[3] > rect2[1])
rect = [0, 0, 1001, 1001]

def main():
	for _ in trange():
		firstCut = listOfNumbers()
		secondCut = listOfNumbers()
		firstPieceArea = abs(firstCut[0] - firstCut[2]) * abs(firstCut[1] - firstCut[3])
		secondPieceArea = abs(secondCut[0] - secondCut[2]) * abs(secondCut[1] - secondCut[3])
		totalPieceArea = firstPieceArea + secondPieceArea
		(bottomLeftX, bottomLeftY) = (max(firstCut[0], secondCut[0]), max(firstCut[1], secondCut[1]))
		(topRightX, topRightY) = (min(firstCut[2], secondCut[2]), min(firstCut[3], secondCut[3]))
		if bottomLeftX < topRightX and bottomLeftY < topRightY:
			emptyPartArea = abs(bottomLeftX - topRightX) * abs(bottomLeftY - topRightY)
			totalPieceArea -= emptyPartArea
		print(totalPieceArea)
main()
exit()


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	(x3, y3, x4, y4) = map(int, input().split())
	d = (x2 - x1) * (y2 - y1) + (x4 - x3) * (y4 - y3)
	b1 = max(x1, x3)
	b2 = max(y1, y3)
	b3 = min(x2, x4)
	b4 = min(y2, y4)
	if b1 < b3 and b2 < b4:
		d -= (b3 - b1) * (b4 - b2)
	print(d)


t = int(input())

def intersection_area(rect1, rect2):
	if rect1[0] > rect2[2] or rect1[2] < rect2[0] or rect1[1] > rect2[3] or (rect1[3] < rect2[1]):
		return 0
	else:
		x = [rect1[0], rect1[2], rect2[0], rect2[2]]
		y = [rect1[1], rect1[3], rect2[1], rect2[3]]
		x.sort()
		y.sort()
		return abs((x[2] - x[1]) * (y[2] - y[1]))
for testcase in range(t):
	cut1 = [int(x) for x in input().split(' ')]
	cut2 = [int(x) for x in input().split(' ')]
	area = (cut1[2] - cut1[0]) * (cut1[3] - cut1[1]) + (cut2[2] - cut2[0]) * (cut2[3] - cut2[1]) - intersection_area(cut1, cut2)
	print(area)