L. Geoland
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer $$$n \ge 3$$$, determine if there exists a non-self-intersecting$$$^\dagger$$$ polygon with $$$n$$$ distinct vertices of integer coordinates such that:

  • no three consecutive vertices of the polygon are collinear;
  • all $$$n$$$ sides are equal.

In case such a polygon exists, provide a construction.

$$$^\dagger$$$ A polygon with $$$n$$$ distinct vertices is non-self-intersecting if no two distinct sides intersect except in the vertices.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The description of the test cases follows.

The first and only line of each test case contains a single integer $$$n$$$ $$$(3 \le n \le 10^4)$$$ — the number of vertices.

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

Output

For each test case:

  • If there is no such polygon, output a single line containing $$$-1$$$.
  • Otherwise, output $$$n$$$ lines the $$$i$$$-th of which contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(-10^9 \le x_i, y_i \le 10^9)$$$, representing that the $$$i$$$-th point of the polygon has coordinates $$$(x_i, y_i)$$$.

If there are multiple possible answers, you may print any of them.

Example
Input
2
3
4
Output
-1
0 0
1 0
1 1
0 1
Note
The polygon is non-self-intersecting but sides are not equal. There exist a pair of three consecutive vertices $$$[6, 1, 2]$$$ and $$$[2, 3, 4]$$$ which are collinear. The polygon is self-intersecting, as there exist two distinct sides $$$[3, 4]$$$ and $$$[5, 6]$$$ that intersect in a non-vertex point.