A. Расстановка прямоугольников
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы раскрашиваете бесконечную клетчатую плоскость, на которой все клетки изначально белые. Для этого вам дается $$$n$$$ штампов. Каждый штамп является прямоугольником ширины $$$w_i$$$ и высоты $$$h_i$$$.

Вы примените каждый штамп ровно один раз, чтобы окрасить в чёрный цвет прямоугольник того же размера, что и штамп. Вы не можете поворачивать штамп; каждая клетка должна быть либо полностью покрыта штампом, либо не покрыта. Вы можете использовать штамп на любом прямоугольнике из клеток плоскости, даже если некоторые или все клетки, покрытые областью штампа, уже черные.

Какую минимальную сумму периметров связных областей черных квадратов можно получить после использования всех штампов?

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$).

В $$$i$$$-й из следующих $$$n$$$ строк содержится по два целых числа $$$w_i$$$ и $$$h_i$$$ ($$$1 \le w_i, h_i \le 100$$$).

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

Для каждого набора входных данных выведите одно целое число — минимальную сумму периметров связных областей черных квадратов, которую можно получить после использования всех штампов.

Пример
Входные данные
5
5
1 5
2 4
3 3
4 2
5 1
3
2 2
1 1
1 2
1
3 2
3
100 100
100 100
100 100
4
1 4
2 3
1 5
3 2
Выходные данные
20
8
10
400
16
Примечание

В первом наборе входных данных можно использовать штампы, как показано слева. Каждый штамп выделен своим цветом для наглядности.

После использования всех штампов осталась одна черная область (как показано справа), периметр которой равен $$$20$$$. Можно показать, что не существует способа использования штампов, который дал бы меньший общий периметр.

Во втором наборе входных данных второй и третий штампы могут быть использованы полностью внутри первого, поэтому ответ — $$$8$$$.