D. Unit Distance!?
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Construct a set of $$$n$$$ points in the Euclidean plane such that:

  • The absolute values of both coordinates of every point are at most $$$10^5$$$;
  • Each coordinate of every point becomes an integer when multiplied by $$$10^{13}$$$;
  • The distance between any two points is at least $$$10^{-4}$$$;
  • At least $$$\left\lfloor \frac12 n\log_2 n-n \right\rfloor$$$ distinct unordered pairs of points have distance in $$$[1-10^{-9},1+10^{-9}]$$$.
Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 100$$$), the number of test cases.

Each test case contains one integer $$$n$$$ ($$$2 \le n \le 5000$$$), the number of points to construct.

The sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output $$$n$$$ lines. The $$$i$$$-th line contains two integers $$$X_i,Y_i$$$ ($$$-10^{18} \le X_i,Y_i \le 10^{18}$$$), representing the actual point $$$\left(\frac{X_i}{10^{13}},\frac{Y_i}{10^{13}}\right)$$$.

Your output is accepted if and only if it satisfies this format and all four conditions above.

If several valid constructions exist, output any one of them.

Example
Input
1
3
Output
0 0
0 10000000000000
8660254037844 5000000000000
Note

Sample 1 Explanation

In the first test case, the actual coordinates are:

$$$$$$ (x_1, y_1) = (0, 0), (x_2, y_2) = (1, 0), (x_3, y_3) = (0.5, 0.8660254038) $$$$$$

The first three conditions are easy to verify. The pairwise distances are:

$$$$$$ d_{12} = 1, d_{13} = d_{23} = 1.000000000013476527219909191607\ldots = 1 + 1.3476 \times 10^{-11} $$$$$$ Thus every pairwise distance is within the allowed tolerance of $$$1$$$, satisfying the fourth condition.