eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Прямоугольники

Прямоугольники

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

На плоскости расположено несколько прямоугольников. Каждый прямоугольник на плоскости задается координатами левого нижнего угла (x_1, y_1) и правого верхнего угла (x_2, y_2), при этом стороны прямоугольников параллельны осям координат. При наложении друг на друга прямоугольники образуют фигуры, отдельно расположенный прямоугольник - тоже фигура. Прямоугольники, соприкасающиеся только углами, не образуют фигуру. Если прямоугольники соприкасаются сторонами, то они тоже образуют фигуру. Требуется определить фигуру максимальной площади (в качестве ответа вывести площадь такой фигуры).

Входные данные

Первая строка содержит количество тестов. В первой строке каждого теста записано количество прямоугольников n, далее идут n строк с координатами вершин прямоугольников x_1 y_1 x_2 y_2. Координаты вершин - целые, неотрицательные числа, в диапазоне от 0 до 100 включительно. Количество прямоугольников не больше 25.

Выходные данные

Для каждого теста в отдельной строке вывести найденную площадь.

Пример

Входные данные #1
2
2
15 15 25 25
10 10 20 20
5
1 1 6 2
2 1 3 5
2 4 7 5
6 2 7 5
8 4 10 7
Выходные данные #1
175
14
Источник Школа Программиста, Красноярский край, Пятая командная олимпиада, 15 ноября 2009, Задача B