B. Different Distances
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Construct an array of $$$4 \cdot n$$$ integers such that:

  • each number $$$1, 2, \dots, n$$$ appears in the array exactly $$$4$$$ times;
  • let $$$p_{x, i}$$$ be the position of the $$$i$$$-th occurrence of number $$$x$$$ in the array; then, for each $$$x$$$ from $$$1$$$ to $$$n$$$, the numbers $$$(p_{x, 2} - p_{x, 1}), (p_{x, 3} - p_{x, 2}), (p_{x, 4} - p_{x, 3})$$$ must be pairwise distinct.

For example, for $$$n = 3$$$, one possible array is $$$[1, 1, 2, 1, 2, 3, 1, 3, 2, 2, 3, 3]$$$, because:

  • $$$p_{1, 2} - p_{1, 1} = 1, p_{1, 3} - p_{1, 2} = 2, p_{1, 4} - p_{1, 3} = 3$$$ — all numbers are distinct;
  • $$$p_{2, 2} - p_{2, 1} = 2, p_{2, 3} - p_{2, 2} = 4, p_{2, 4} - p_{2, 3} = 1$$$ — all numbers are distinct;
  • $$$p_{3, 2} - p_{3, 1} = 2, p_{3, 3} - p_{3, 2} = 3, p_{3, 4} - p_{3, 3} = 1$$$ — all numbers are distinct.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.

The only line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 200$$$).

Output

For each test case, output the required array. If there are several suitable arrays, output any of them. It can be shown that at least one suitable array always exists under the constraints of the problem.

Example
Input
3
3
4
5
Output
1 1 2 1 2 3 1 3 2 2 3 3
1 4 3 4 4 3 3 1 2 1 2 3 4 2 2 1 
5 3 2 4 1 2 2 4 4 5 3 5 2 1 3 1 5 4 1 3