The Cable Car

A cable car runs up a mountain in a perfectly straight line. Along the way it passes $n$ pylons, and every pylon stands somewhere on that same line.

The engineer who surveyed the mountain wrote the pylons down in whatever order he walked into them, which is not the order the cabin passes them. He did note one thing though: the first two pylons in his list are written in the order the cabin meets them, so together they tell you which way the cabin travels.

Your task is to put the whole list back into travel order.

Input

The first line contains a single integer $t$ - the number of testcases.

• The first line of each testcase contains a single integer $n$ - the number of pylons.
• Each of the next $n$ lines contains two integers $x_i$ and $y_i$ - the position of one pylon.

All $n$ pylons in a testcase are distinct and lie on one straight line. The cabin travels from the first pylon in the list towards the second one.

Output

For every testcase print $n$ lines, the positions of the pylons in the order the cabin passes them, two integers per line.

Example

2
5
9 4
5 2
15 7
7 3
13 6
4
0 0
0 5
0 -3
0 9

15 7
13 6
9 4
7 3
5 2
0 -3
0 0
0 5
0 9

In the first testcase the cabin goes from $(9,4)$ towards $(5,2)$, so it travels down and to the left and the pylon at $(15,7)$ is the one it meets first. In the second testcase the line is vertical, so the order has nothing to do with $x$ at all.

Constraints

$1\le t\le 10$
$3\le n\le 5\cdot 10^4$
$-10^6\le x_i,y_i\le 10^6$
$n_1+n_2+\dots +n_t\le 10^5$

This problem was adapted, with permission, from Sortiranje duž linije, authored by Društvo matematičara Srbije and Fondacija Petlja.