311023: CF1922E. Increasing Subsequences

E. Increasing Subsequencestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Let's recall that an increasing subsequence of the array $a$ is a sequence that can be obtained from it by removing some elements without changing the order of the remaining elements, and the remaining elements are strictly increasing (i. e $a_{b_1} < a_{b_2} < \dots < a_{b_k}$ and $b_1 < b_2 < \dots < b_k$). Note that an empty subsequence is also increasing.

You are given a positive integer $X$. Your task is to find an array of integers of length at most $200$, such that it has exactly $X$ increasing subsequences, or report that there is no such array. If there are several answers, you can print any of them.

If two subsequences consist of the same elements, but correspond to different positions in the array, they are considered different (for example, the array $[2, 2]$ has two different subsequences equal to $[2]$).

Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The only line of each test case contains a single integer $X$ ($2 \le X \le 10^{18}$).

Output

For each query, print the answer to it. If it is impossible to find the required array, print -1 on the first line. Otherwise, print a positive integer $n$ on the first line — the length of the array. On the second line, print $n$ integers — the required array itself. If there are several answers, you can print any of them. All elements of the array should be in the range $[-10^9; 10^9]$.

ExampleInput

4
2
5
13
37

Output

1
0
3
0 1 0
5
2 2 3 4 2
7
-1 -1 0 0 2 3 -1

题目大意：
E. 递增子序列
给定一个数组a，它的递增子序列可以通过删除一些元素得到，同时保持剩余元素的顺序，并且剩余元素严格递增（即\(a_{b_1} < a_{b_2} < \dots < a_{b_k}\) 且 \(b_1 < b_2 < \dots < b_k\)）。注意，空子序列也是递增的。

给定一个正整数X，任务是找到一个长度最多为200的整数数组，使得它恰好有X个递增子序列，或者报告没有这样的数组。如果有多个答案，可以输出其中任何一个。

如果两个子序列包含相同的元素但对应数组中的不同位置，则认为它们是不同的（例如，数组\[2, 2\]有两个不同的子序列等于\[2\]）。

输入数据格式：
第一行包含一个整数t（\(1 \le t \le 1000\)）——测试用例的数量。
每个测试用例仅包含一行，有一个整数X（\(2 \le X \le 10^{18}\)）。

输出数据格式：
对于每个查询，打印它的答案。如果不可能找到所需的数组，则在第一行打印-1。否则，在第一行打印一个正整数n——数组的长度。在第二行，打印n个整数——所需的数组本身。如果有多个答案，可以输出其中任何一个。数组的所有元素应该在范围\([-10^9; 10^9]\)内。

示例：
输入
```
4
2
5
13
37
```
输出
```
1
0
3
0 1 0
5
2 2 3 4 2
7
-1 -1 0 0 2 3 -1
```题目大意： E. 递增子序列 给定一个数组a，它的递增子序列可以通过删除一些元素得到，同时保持剩余元素的顺序，并且剩余元素严格递增（即\(a_{b_1} < a_{b_2} < \dots < a_{b_k}\) 且 \(b_1 < b_2 < \dots < b_k\)）。注意，空子序列也是递增的。 给定一个正整数X，任务是找到一个长度最多为200的整数数组，使得它恰好有X个递增子序列，或者报告没有这样的数组。如果有多个答案，可以输出其中任何一个。 如果两个子序列包含相同的元素但对应数组中的不同位置，则认为它们是不同的（例如，数组\[2, 2\]有两个不同的子序列等于\[2\]）。 输入数据格式： 第一行包含一个整数t（\(1 \le t \le 1000\)）——测试用例的数量。 每个测试用例仅包含一行，有一个整数X（\(2 \le X \le 10^{18}\)）。 输出数据格式： 对于每个查询，打印它的答案。如果不可能找到所需的数组，则在第一行打印-1。否则，在第一行打印一个正整数n——数组的长度。在第二行，打印n个整数——所需的数组本身。如果有多个答案，可以输出其中任何一个。数组的所有元素应该在范围\([-10^9; 10^9]\)内。 示例： 输入 ``` 4 2 5 13 37 ``` 输出 ``` 1 0 3 0 1 0 5 2 2 3 4 2 7 -1 -1 0 0 2 3 -1 ```