write a go solution for Description:
You are given an integer n. You choose n cells (x_1,y_1),(x_2,y_2),...,(x_n,y_n) in the grid nxn where 1<=x_i<=n and 1<=y_i<=n.

Let mathcalH be the set of distinct Manhattan distances between any pair of cells. Your task is to maximize the size of mathcalH. Examples of sets and their construction are given in the notes.

If there exists more than one solution, you are allowed to output any.

Manhattan distance between cells (x_1,y_1) and (x_2,y_2) equals |x_1-x_2|+|y_1-y_2|.

Input Format:
The first line contains a single integer t (1<=t<=50) — the number of test cases.

Each of the following t lines contains a single integer n (2<=n<=10^3).

Output Format:
For each test case, output n points which maximize the size of mathcalH. It is not necessary to output an empty line at the end of the answer for each test case.

Note:
In the first testcase we have n=2. One of the possible arrangements is:

The arrangement with cells located in (1,1) and (1,2).

In the second testcase we have n=3. The optimal arrangement is:

The arrangement with cells located in (2,1), (2,3) and (3,1).

mathcalH=|2-2|+|1-1|,|2-2|+|3-3|,|3-3|+|1-1|,|2-2|+|1-3|,|2-3|+|1-1|,|2-3|+|3-1|=0,0,0,2,1,3=0,1,2,3.

For n=4 a possible arrangement is:

For n=5 a possible arrangement is:

For n=6 a possible arrangement is:. Output only the code with no comments, explanation, or additional text.