CF1819B The Butcher

Anton 玩他最喜欢的游戏“Defense of The Ancients 2”，他最喜欢的英雄是 The Butcher。现在他想做自己的晚餐。为此，他会取一个高为 $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$ 个矩形是切割得到的，最后一个是 Butcher 在所有 $n-1$ 次切割后剩下的那个。 不幸的是，Butcher 忘记了 $h$ 和 $w$ 的具体数值，但他手上还有 $n$ 个混合顺序的矩形。注意，Butcher 没有旋转这些矩形，只是打乱了它们的顺序。现在他想知道，所有可能的 $(h, w)$ 对有哪些，可以从这些矩形中得到。你需要帮助他找出所有可能的 $(h, w)$ 对！ 保证至少存在一组 $(h, w)$ 能得到这组矩形。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示获得的矩形数量。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^6$），表示第 $i$ 个矩形的高和宽。 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，第一行输出一个整数 $m$，表示所有可能的 $(h, w)$ 对的数量。 接下来的 $m$ 行，每行输出两个整数 $h_i$ 和 $w_i$，表示可以得到这些矩形的原始矩形的高和宽。输出顺序不限。

在第一个测试点中，Butcher 只能有一个 $4 \times 5$ 的矩形。切割过程如下（先是绿色切割，再是红色切割）：  在第二个测试点中，Butcher 可能有 $1 \times 3$ 或 $3 \times 1$ 的矩形。切割过程如下（先是绿色切割，再是红色切割）：  在第三个测试点中，Butcher 没有进行任何切割，所以原始矩形是 $10 \times 10$。 由 ChatGPT 4.1 翻译