你需要按某种顺序就一系列重要的历史事件进行讲座，每个讲座对应一个事件。每个事件持续的时间间隔为 $[a_i, b_i]$。如果两个事件的时间间隔有公共点，我们称这两个事件是相关的。将相关的事件安排在彼此接近的时间进行讲座会比较方便。此外，不相关事件的讲座应按照事件发生的先后顺序进行（如果事件 A 先于不相关事件 B 发生，则 A 的讲座应先于 B 的讲座）。

请找到最小的整数 $k \ge 0$ 以及一种讲座顺序，使得任意两个相关事件的讲座间隔不超过 $k$（讲座编号 $i$ 和 $j$ 的间隔被视为 $|i - j|$）。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述： 每个测试用例的第一行包含数字 $n$，$1 \le n \le 50\,000$。接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，$-10^9 \le a_i \le b_i \le 10^9$，表示第 $i$ 个事件的时间间隔。所有区间互不相同。

输出格式

按输入顺序输出每个测试用例的答案。每个测试用例答案的第一行应包含最小的 $k$ 值。接下来的 $n$ 行应按某种顺序输出这些区间（格式与输入相同），使得任意两个相关事件的讲座间隔不超过 $k$。请记住，不相关的区间也必须按正确的顺序排列！

样例

输入 1

1
3
1 6
2 3
4 5

输出 1

1
2 3
1 6
4 5