Background

Little U is very interested in functions that map a set to a number, and $\text{mex}$ is a good example.

$\text{mex}(S)$ is the smallest non-negative integer that does not appear in the set $S$.

Problem Description

Multiple test cases.

For each test case, given $c$, you need to construct a sequence $a_1,a_2,\ldots,a_n \in [0,2\times 10^9]$ such that

$$\sum\limits_{1\le l\le r\le n}\text{mex}(a_l,a_{l+1},\ldots,a_r)=c$$

where it is required that $1 \le n \le 3000$. It can be proven that within the constraints of this problem, if a solution exists, then a solution must exist with $1 \le n \le 3000$.

Input Format

The first line contains an integer $T$, the number of test cases.

Then $T$ lines follow, each containing one non-negative integer $c$.

Output Format

For each test case:

If there is no solution, output only one line containing an integer $-1$.

Otherwise, output a positive integer $n$ on the first line.

Output $n$ non-negative integers $a_1,a_2,\ldots,a_n$ on the second line.

4
13
25
32
0

7
1 9 1 9 8 1 0
13
1 1 4 5 1 4 1 9 1 9 8 1 0
8
1 2 3 9 0 7 3 8
7
1 2 3 9 7 3 8

Hint

Sample Explanation

For sample #1: only $\text{mex}(a_7)=1$, and for all $1\le i\le6$, we have $\text{mex}(a_i,a_{i+1},\ldots,a_7)=2$, so the total sum is $13$.

Constraints

$id$ is the $\text{subtask}$ index.

$id$	Special Property	Score	$id$	Special Property	Score
$1$	$c\le3\times10^3$	$3$	$5$	$c\le8\times 10^6$	$10$
$2$	$c\le6\times 10^3$	$7$	$6$	$c\le1\times 10^8$
$3$	$c\le8\times10^4$	$10$	$7$	$c\le1\times 10^9$	$25$
$4$	$c\le4\times 10^6$	$15$	$8$	$c\le2\times 10^9$	$20$

For $100\%$ of the testdata, $T\le 310$, $0\le c\le 2\times 10^9$.

Translated by ChatGPT 5