B. Мясник
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антон играет в свою любимую игру «Защита древних 2» за своего любимого героя — Мясника. Сейчас он хочет приготовить себе ужин. Для этого он возьмет прямоугольник высоты $$$h$$$ и ширины $$$w$$$, затем проведет вертикальный или горизонтальный разрез так, чтобы обе получившиеся части имели целые стороны. После этого одну из частей он положит в ящик, а другую снова разрежет, и так далее.

Более формально, прямоугольник размера $$$h \times w$$$ можно разрезать на две части размеров $$$x \times w$$$ и $$$(h - x) \times w$$$, где $$$x$$$ является целым числом от $$$1$$$ до $$$(h - 1)$$$, или же на две части размеров $$$h \times y$$$ и $$$h \times (w - y)$$$, где $$$y$$$ является целым числом от $$$1$$$ до $$$(w - 1)$$$.

Эту операцию он повторит $$$n - 1$$$ раз, после чего оставшийся прямоугольник тоже положит в ящик. Таким образом, в ящике будет $$$n$$$ прямоугольников, из которых $$$n - 1$$$ прямоугольник был отложен в результате разрезов, а $$$n$$$-й прямоугольник — тот, что остался в руках Мясника после всех $$$n - 1$$$ разрезов.

К сожалению, Мясник забыл числа $$$h$$$ и $$$w$$$, однако у него сохранились $$$n$$$ прямоугольников, перемешанных в произвольном порядке. Обратите внимание, что Мясник не поворачивал прямоугольники, но, возможно, переупорядочил их. Теперь он хочет узнать все возможные пары $$$(h, w)$$$, из которых можно получить данный набор прямоугольников. А вы должны ему в этом помочь!

Гарантируется, что существует хотя бы одна пара $$$(h, w)$$$, из которой можно получить данный набор прямоугольников.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество полученных прямоугольников.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$) — высота и ширина $$$i$$$-го прямоугольника.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

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

Пример
Входные данные
4
3
1 2
3 5
1 3
3
1 1
1 1
1 1
1
10 10
4
3 2
5 5
2 2
8 7
Выходные данные
1
4 5
2
1 3
3 1
1
10 10
1
13 7
Примечание

В первом наборе входных данных у Мясника мог быть только прямоугольник размером $$$4 \times 5$$$. Тогда разрезы могли бы выглядеть следующим образом (сначала был сделан зеленый разрез, затем красный):

Во втором наборе входных данных у Мясника мог быть либо прямоугольник размером $$$1 \times 3$$$, либо $$$3 \times 1$$$. Разрезы выглядели бы так (сначала был сделан зеленый разрез, затем красный):

В третьем наборе входных данных Мясник не делал ни одного разреза, поэтому прямоугольник имеет размер $$$10 \times 10$$$.