Construct Sequence with Specified (\mathrm{mex}) Sum

You are given an integer \(c\). Your task is to construct a sequence of \(n\) integers \(a_1,a_2,\dots,a_n\) (with \(1 \le n \le 3000\)) such that each \(a_i\) is in the range \([0,2\times10^9]\) and

[ \sum_{1\le l\le r\le n} \mathrm{mex}(a_l,a_{l+1},\dots,a_r)= c ]

Recall that the mex (minimum excludant) of a set of non–negative integers is the smallest nonnegative integer that does not belong to the set.

It can be shown that if there exists any solution the there is one with \(1\le n\le3000\). It is also guaranteed that the input \(c\) (which may be 0) is such that a solution exists.

Note: A common strategy is to construct a sequence made up only of 0's and another nonzero number (say 2). In any subarray the mex is 0 if there is no 0, and 1 if at least one 0 appears. In a sequence of length \(n\) the total number of subarrays is \[ T(n)=\frac{n(n+1)}2. \] If the sequence is binary (with 0 indicating a "marker" and nonzero otherwise) then the overall sum equals \[ T(n)-\sum_{\text{ones-blocks}} \frac{L(L+1)}2, \] so that by choosing the positions of the zeros appropriately one can achieve any value among those that are representable. One simple idea is as follows.

• If \(c=0\) output a sequence with no 0 (for example, a single element equal to 2).
• If \(c\) is small (say between 1 and \(n\) for some \(n\le3000\)), one may take the sequence \(a=[0, 2,2,\dots,2]\). In that case every subarray that contains the 0 gives mex 1 and the others give 0. The number of subarrays that contain the first element is exactly \(n\) (because any subarray starting at index 1 contains the only 0) so that the sum is \(n\).
• In general one may try to use a solution with exactly one 0 or with two 0's. For a sequence with exactly one 0 at position \(i\) (and all other elements nonzero) the answer is \[ i \times (n-i+1), \] and for two 0's (say at positions \(i<j\)) the sum is \[ T(n)-\Bigl(T(i-1)+T(j-i-1)+T(n-j)\Bigr) \quad\text{ where } T(x)=\frac{x(x+1)}2. \] One may simply search for an appropriate \(n\) (with \(1\le n\le3000\)) and for positions for the 0's so that the sum is exactly \(c\).

Your program must output any valid sequence.

inputFormat

The input consists of multiple test cases. The first line contains a single integer \(T\) (the number of test cases). Each of the following \(T\) lines contains one nonnegative integer \(c\) indicating the target sum of mex's.

It is guaranteed that for each \(c\) a solution exists with \(1\le n\le3000\).

outputFormat

For each test case, output two lines. In the first line output \(n\) (the length of the sequence). In the second line output \(n\) space–separated integers \(a_1,a_2,\dots,a_n\). If there are multiple answers, output any one.

sample

1
0

1
2