Description

Input

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

Output

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

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

$\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: