8669: Maximum Triangles

We called a triangle is good if and only If the triangle contains the origin.

You need to find n points on the plane, satisfying:

• None any two of them and the origin should be collinear.
• The coordinates of each point should be an integer and in the range [-50000,50000]
• Under the above limits, the number of good triangles made up of those n points should be maximized.

Output the maximum number and a set of the coordinates of those n points for which the maximum is reached.

The first line of input contains a single integer $T(1\le T\le 10)$, indicating the number of test cases.

Each of the next T lines contains a single integer n(1≤n≤2×105), describing the number of points you have to find for that test case.

It is guaranteed that the sum of n over all test cases does not exceed 10^6.

1
3

1
0 1
-1 -1
1 -1