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\leq T\leq 10)$, indicating the number of test cases.

Each of the next $T$ lines contains a single integer $n(1\leq n\leq 2\times 10^5)$, 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$.

For each test case print $(n+1)$ lines. The first line should contain a single integer, denoting the maximum number of good triangles. The $i$-th of the next $n$ lines should contain two space-separated integers $x_i,y_i(|x_i|,|y_i|\leq 50000)$, denoting the coordinates of the $i$-th point of the set. If there are multiple solutions, output any.

1
3

1
0 1
-1 -1
1 -1

2022“杭电杯”中国大学生算法设计超级联赛（10）