Антон играет в свою любимую игру «Защита древних 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)\), из которой можно получить данный набор прямоугольников.
Выходные данные
Для каждого набора входных данных в первой строке выведите одно целое число \(m\) — количество пар \((h, w)\), обозначающих размеры прямоугольников, из которых можно получить данные прямоугольники. Два прямоугольника считаются различными, если у них отличается длина или ширина.
В каждой из следующих \(m\) строк выведите два целых числа \(h_i\) и \(w_i\) — высоту и ширину прямоугольника, из которого можно получить данные прямоугольники. Вы можете выводить прямоугольники в любом порядке.
Примечание
В первом наборе входных данных у Мясника мог быть только прямоугольник размером \(4 \times 5\). Тогда разрезы могли бы выглядеть следующим образом (сначала был сделан зеленый разрез, затем красный):
Во втором наборе входных данных у Мясника мог быть либо прямоугольник размером \(1 \times 3\), либо \(3 \times 1\). Разрезы выглядели бы так (сначала был сделан зеленый разрез, затем красный):
В третьем наборе входных данных Мясник не делал ни одного разреза, поэтому прямоугольник имеет размер \(10 \times 10\).