311305: CF1968E. Cells Arrangement

You are given an integer $n$. You choose $n$ cells $(x_1,y_1), (x_2,y_2),\dots,(x_n,y_n)$ in the grid $n\times n$ where $1\le x_i\le n$ and $1\le y_i\le n$.

Let $\mathcal{H}$ be the set of distinct Manhattan distances between any pair of cells. Your task is to maximize the size of $\mathcal{H}$. 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|$.

The first line contains a single integer $t$ ($1\le t\le 50$) — the number of test cases.

Each of the following $t$ lines contains a single integer $n$ ($2\le n\le 10^3$).

For each test case, output $n$ points which maximize the size of $\mathcal{H}$. It is not necessary to output an empty line at the end of the answer for each test case.

5
2
3
4
5
6

1 1
1 2

2 1
2 3
3 1

1 1
1 3
4 3
4 4

1 1
1 3
1 4
2 1
5 5

1 4
1 5
1 6
5 2
5 5
6 1

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)$.

$\mathcal{H}$=$\{|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: