#864 Murimuri Sequence

Statement

Statement language

You are given an integer $N$ . Using every integer from $-N$ to $N$ exactly once, construct a sequence $A_1,A_2,\ldots,A_{2N+1}$ satisfying the following condition.

For every integer $i$ with $3\leq i\leq2N+1$ , there must be at least one real number $x$ satisfying

A_{i-2}x^2+A_{i-1}x+A_i=0.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print a valid sequence $A_1,A_2,\ldots,A_{2N+1}$ on one line, separated by spaces.

Constraints

$1\leq T\leq100\,000$ .
$1\leq N\leq200\,000$ .
The sum of $N$ over all test cases is at most .

Subtasks

#	Score	Constraints
1	7	$N\leq3$ .
2	93	No additional constraints.

Samples

Input

2
1
3

Output

1 0 -1
-3 -2 1 0 -1 2 3

2번째 테스트 케이스에서는 $i=3,4,5,6,7$ 일 때 $x=-1,0,1,2,3$ 을 각각 해로 가진다.