310332: CF1819B. The Butcher

B. The Butchertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

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

Output

1
4 5
2
1 3
3 1
1
10 10
1
13 7

Note

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$.

**题目大意：**

题目描述了一个关于将矩形切割成多个小矩形的问题。开始时，有一个高为 $ h $、宽为 $ w $ 的矩形。可以进行 $ n-1 $ 次切割，每次切割可以将矩形切成两个部分，一部分是 $ x \times w $ 和另一部分是 $ (h - x) \times w $，其中 $ x $ 是从 1 到 $ h-1 $ 的整数；或者切成两个部分 $ h \times y $ 和 $ h \times (w - y) $，其中 $ y $ 是从 1 到 $ w-1 $ 的整数。切割完成后，将最后剩下的矩形也放入盒子中，这样盒子里就有 $ n $ 个矩形。

但是，现在布彻（Butcher）忘记了原始矩形的高 $ h $ 和宽 $ w $ 的具体数值，他只记得切割后得到的 $ n $ 个矩形，这些矩形已经随机排列。布彻没有旋转这些矩形，只是将它们打乱顺序。现在他想要知道所有可能的 $ (h, w) $ 对，使得可以从这些矩形切割得到。保证至少存在一个这样的 $ (h, w) $ 对。

**输入数据格式：**

每个测试案例包含多个测试。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) —— 测试案例的数量。接下来是每个测试案例的描述。

每个测试案例的第一行包含一个整数 $ n $ ($ 1 \le n \le 2 \cdot 10^5 $) —— 获得的矩形数量。

接下来 $ 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 $ —— 可以得到给定矩形的矩形的高和宽。**题目大意：** 题目描述了一个关于将矩形切割成多个小矩形的问题。开始时，有一个高为 $ h $、宽为 $ w $ 的矩形。可以进行 $ n-1 $ 次切割，每次切割可以将矩形切成两个部分，一部分是 $ x \times w $ 和另一部分是 $ (h - x) \times w $，其中 $ x $ 是从 1 到 $ h-1 $ 的整数；或者切成两个部分 $ h \times y $ 和 $ h \times (w - y) $，其中 $ y $ 是从 1 到 $ w-1 $ 的整数。切割完成后，将最后剩下的矩形也放入盒子中，这样盒子里就有 $ n $ 个矩形。 但是，现在布彻（Butcher）忘记了原始矩形的高 $ h $ 和宽 $ w $ 的具体数值，他只记得切割后得到的 $ n $ 个矩形，这些矩形已经随机排列。布彻没有旋转这些矩形，只是将它们打乱顺序。现在他想要知道所有可能的 $ (h, w) $ 对，使得可以从这些矩形切割得到。保证至少存在一个这样的 $ (h, w) $ 对。 **输入数据格式：** 每个测试案例包含多个测试。第一行包含一个整数 $ t $ ($ 1 \le t \le 10^4 $) —— 测试案例的数量。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数 $ n $ ($ 1 \le n \le 2 \cdot 10^5 $) —— 获得的矩形数量。 接下来 $ 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 $ —— 可以得到给定矩形的矩形的高和宽。