You are given a set $$$S$$$ of $$$n$$$ integer lattice points in the plane. Find a simple lattice polygon with no $$$180$$$ degree angles that contains each point in $$$S$$$ as a vertex.
For example, here is an example of the set $$$S$$$ and a valid polygon:
The below polygon would NOT be valid, because of the $$$180$$$ degree angle at $$$(5, 3)$$$.
The polygon must be simple, meaning its edges may only intersect at vertices, and all of its vertices must be at lattice points, but it does not have to be convex, as shown in the example.
Each test consists of multiple test cases.
The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 2\cdot10^5$$$) — the number of test cases.
The first line of each test case consists of a single integer $$$n$$$ ($$$1\leq n\leq2\cdot10^5$$$) — the size of $$$S$$$.
The $$$i$$$th of the next $$$n$$$ lines of each test case consists of two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^8\leq x,\,y\leq10^8$$$) — the coordinates of the $$$i$$$-th element of $$$S$$$. It is guaranteed that all points in $$$S$$$ are distinct.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.
The first line of output for each test case should consist of a single integer $$$m$$$ ($$$3\leq m \leq 10\cdot n$$$) — the number of vertices of the polygon. You do not need to minimize $$$m$$$.
The $$$i$$$th of the next $$$m$$$ lines should consist of two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9\leq x_i,\, y_i\leq 10^9$$$) — the coordinates of the $$$i$$$-th vertex of the polygon. All the vertices of $$$S$$$ should be among these.
Under the given input conditions, it can be shown that there exists a solution with the given restrictions on $$$m$$$ and $$$(x_i, y_i)$$$.
If there are multiple solutions, you may print any.
252 43 64 45 36 240 01 02 03 0
7 2 4 3 6 4 4 5 3 6 3 6 2 2 2 6 0 0 1 0 1 1 2 0 3 0 3 -1
The first test case corresponds to the image above.
Here are the points and polygon for the second test case:
