Given an array \(a\) with elements numbered from \(1\) to \(100\). Initially, \(a_i = 0\) for \(1 \leq i < 100\), and the last element \(a_{100}\) is equal to \(1\).

The array \(a\) can be modified using increment operations. To perform \(m\) increment operations, it is necessary to select \(m\) integers \(p_1, p_2, \dots, p_m\) (\(1\le p_i < 100\)) and sequentially execute assignments \(a_{p_i} \leftarrow (a_{p_i} + a_{p_i + 1})\) for \(i\) from \(1\) to \(m\).

Given an integer \(n\), find the sequence of increment operations after which the element at the first position in array \(a\) becomes equal to \(n\).

Input

The first line contains two integers \(t\) and \(g\) (\(1 \le t \le 100\), \(0 \leq g \leq 5\)) — the number of input sets and the test block number, respectively.

In the next \(t\) lines, there is a single integer \(n\) (\(1 \le n \le 10^{18}\)) — the value that \(a_1\) should be equal to after performing the increment operations in the corresponding set.

Output

For each set of input data, output one integer \(m\) (\(0 \leq m \leq 2000\)) in the first line — the number of increase operations.

In the second line, output \(m\) integers \(p_i\) (\(1 \le p_i < 100\)) — the parameters of the increase operations.

If there are multiple correct answers, you can output any of them.

Scoring

The first four test blocks allow using no more than 300 increment operations.

1. (\(4\) points): \(n \leq 100\);

2. (\(6\) points): \(n = k^2\) for some integer \(1 \le k \le 100\);

3. (\(10\) points): \(n = (2^k - 1)\) for some integer \(k\);

4. (\(13\) points): \(n\) is a Fibonacci number (i.e., \(n\) is an element of the sequence where each element is the sum of the two previous ones: \(1, 1, 2, 3, 5, 8, 13, 21, 34, \dots\));

5. (up to \(67\) points): without additional restrictions. Let the maximum number of increment operations used be \(c\). If \(c \le 300\), you will receive \(67\) points, otherwise you will receive (\(17 + \left \lfloor \frac{2000 - c}{34} \right \rfloor\)) points.

The C++ code that calculates the number of points for the last test block depending on the number of increment operations used is:

((c <= 300) ? 67 : (17 + (2000 - c) / 34))

Samples

Input 1

1 0
1

Output 1

99
99 98 ... 7 6 5 4 3 2 1

Input 2

2 0
3
16

Output 2

101
99 98 ... 7 6 5 4 3 2 1 1 1
103
99 98 ... 7 6 5 4 4 3 3 2 2 1 1

Notes

For clarity, the examples of the input data in the problem statement have been reduced. To obtain the correct answer, replace "..." with the sequence of integers from \(97\) to \(8\).

Let's consider the second set of input data for the second example, where \(n = 16\). The first 8 elements of the array \(a\) after performing the next operation look as follows:

• \(p_1\) = 99, \(a = [0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0, 0, 1, 1]\);

• \(p_2\) = 98, \(a = [0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0, 1, 1, 1]\);

• \(\ldots\)

• \(p_{93} = 7\), \(a = [0, 0, 0, 0, 0, 0, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{94} = 6\), \(a = [0, 0, 0, 0, 0, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{95} = 5\), \(a = [0, 0, 0, 0, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{96} = 4\), \(a = [0, 0, 0, 1, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{97} = 4\), \(a = [0, 0, 0, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{98} = 3\), \(a = [0, 0, 2, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{99} = 3\), \(a = [0, 0, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{100} = 2\), \(a = [0, 4, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{101} = 2\), \(a = [0, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{102} = 1\), \(a = [8, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\);

• \(p_{103} = 1\), \(a = [16, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]\).