В современном мире шпионаж в других странах осуществляется с использованием спутников и беспилотных летательных аппаратов, оснащенных камерами. Все эти фотографии различных размеров и из различных источников могут быть объединены, чтобы дать представление о стране в целом.
По имеющимся фотографиям (прямоугольным площадям, так как содержимое фотографий является сверхсекретной информацией) следует выяснить общую площадь фотографируемого пространства. Обратите внимание, что некоторые области могут появляться на нескольких фотографиях и должны учитываться только один раз.
Первая строка содержит количество тестов, не более 100. Далее для каждого теста:
в первой строке находится количество фотографий n (1 ≤ n ≤ 1000).
n строк с четырьмя целыми числами x[1]
, y[1]
, x[2]
и y[2]
(0 ≤ x[1]
, y[1]
, x[2]
, y[2]
≤ 10^6
, x[1]
< x[2]
и y[1]
< y[2]
): координаты юго-западного и северо-восточного угла соответственно для каждой фотографии. Фотографии имеют прямоугольную форму с углами (x[1]
, y[2]
) и (x[2]
, y[1]
).
Координаты соответствуют двумерной плоскости (считаем, что Земля плоская).
Для каждого теста вывести в отдельной строке общую площадь сфотографированного пространства.