CF1819B.The Butcher

Anton plays his favorite game "Defense of The Ancients 2" for his favorite hero — The Butcher. Now he wants to make his own dinner. To do this he will take a rectangle of height $h$ and width $w$, then make a vertical or horizontal cut so that both resulting parts have integer sides. After that, he will put one of the parts in the box and cut the other again, and so on.

More formally, a rectangle of size $h \times w$ can be cut into two parts of sizes $x \times w$ and $(h - x) \times w$, where $x$ is an integer from $1$ to $(h - 1)$, or into two parts of sizes $h \times y$ and $h \times (w - y)$, where $y$ is an integer from $1$ to $(w - 1)$.

He will repeat this operation $n - 1$ times, and then put the remaining rectangle into the box too. Thus, the box will contain $n$ rectangles, of which $n - 1$ rectangles were put in the box as a result of the cuts, and the $n$-th rectangle is the one that the Butcher has left after all $n - 1$ cuts.

Unfortunately, Butcher forgot the numbers $h$ and $w$, but he still has $n$ rectangles mixed in random order. Note that Butcher didn't rotate the rectangles, but only shuffled them. Now he wants to know all possible pairs $(h, w)$ from which this set of rectangles can be obtained. And you have to help him do it!

It is guaranteed that there exists at least one pair $(h, w)$ from which this set of rectangles can be obtained.

安东正在玩他最喜欢的游戏《远古守卫者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)$！

题目保证至少存在一对 $(h, w)$ 可以生成给定的这组矩形。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of rectangles obtained.

The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^6$) — the height and width of the $i$-th rectangle.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示所得矩形的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^6$），分别表示第 $i$ 个矩形的高度和宽度。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, on the first line output a single integer $m$ — the number of pairs $(h, w)$ denoting the sizes of rectangles from which the given rectangles can be obtained. Two rectangles are considered different if they have different heights or widths.

On each of the following $m$ lines print output integers $h_i$ and $w_i$ — the height and width of the rectangle from which the given rectangles can be obtained. You can output the rectangles in any order.

对于每个测试用例，在第一行输出一个整数 $m$ —— 表示能生成给定矩形的所有矩形尺寸 $(h, w)$ 的对数。若两个矩形的高度或宽度不同，则认为它们是不同的矩形。

在接下来的 $m$ 行中，每行输出两个整数 $h_i$ 和 $w_i$ —— 表示能生成给定矩形的矩形的高度和宽度。你可以以任意顺序输出这些矩形。

In the first test case, Butcher could only have a rectangle of size $4 \times 5$. Then the cuts could look like this (first the green cut was made, then the red one):

In the second test case, Butcher could have either a rectangle of $1 \times 3$ or $3 \times 1$. The cuts would have looked like this (first the green cut was made, then the red cut):

In the third test case, Butcher did not make any cuts, so the rectangle is $10 \times 10$.

在第一个测试用例中，屠夫只能得到一个 $4 \times 5$ 的矩形。此时切割过程可能如下所示（先进行绿色切割，再进行红色切割）：

在第二个测试用例中，屠夫可能得到一个 $1 \times 3$ 或 $3 \times 1$ 的矩形。切割过程可能如下所示（先进行绿色切割，再进行红色切割）：

在第三个测试用例中，屠夫未进行任何切割，因此矩形为 $10 \times 10$。