Constructing a Sequence with a Given MEX Sum

You are given an integer c. Your task is to construct a sequence a₁, a₂, ..., a_n with each a_i \in [0, 2\times10^9] and an integer n satisfying 1 \le n \le 40, such that

$$\sum_{\emptyset \neq S \subseteq \{1,2,\ldots,n\}} \mathrm{mex}(\{a_i : i \in S\}) = c. $$

Here, for a set of nonnegative integers, mex is defined as the minimum nonnegative integer not present in the set. For example, mex({0, 1, 3}) = 2 and mex({1, 2}) = 0.

It can be proven that if there exists a solution for a given c (with the data constraints of the problem), then there exists one with 1 \le n \le 40.

Note: The input consists of multiple test cases.

inputFormat

The first line of input contains an integer T (the number of test cases).

Each of the next T lines contains a single integer c.

It is guaranteed that all given test cases satisfy the condition that if a solution exists then there is one with 1 \le n \le 40.

outputFormat

For each test case, if a valid sequence exists, output two lines:

• The first line contains an integer n which is the length of the sequence.
• The second line contains n space-separated integers representing the sequence a₁, a₂, ..., a_n.

If no solution exists, simply output -1 (without quotes) for that test case.

sample

4
0
3
7
1

1
1
2
0 1
3
0 1 1
1
0

</p>