Binary Fun — Eolymp

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) – the number of test cases.

The only line of each test case contains two integers $n, k$ ( $1 \leq n \leq 1 0^{18}$ 1 \le n \le 10^{18} and $1 \leq k \leq 60$ 1 \le k \le 60) – the desired integer, and the definition parameter.

Output

For each test case, if such $a_{1}, a_{2}, \dots, a_{m}$ a_1, a_2, \dots, a_m exist:

The first line contains minimal $m$ .
The second line contains $m$ separated integers $a_{1}, a_{2}, \dots, a_{m}$ a_1, a_2, \dots, a_m in sorted manner.

Otherwise, output $- 1$ .

Examples

Example 1

Loading

Note

In the first test, it can be shown that the optimal solution is: $3 \oplus 12 = 15$ 3 \oplus 12 = 15

$3 = (11)_{2}$ 3 = (\textbf{11})_2 is a $2$ -special integer.
$12 = (1100)_{2}$ 12 = (\textbf{1100})_2 is a $2$ -special integer.

0011 \oplus 11001111

\begin{matrix} 00\textbf{11} \\ \oplus \\ \textbf{11}00 \\ \hline \textbf{1111} \end{matrix}

which stands for $1 + 2 + 2^{2} + 2^{3} = 15$ 1 + 2 + 2^2 + 2^3 = 15.

In the second test, it can be shown that this is the optimal construction:

$7 = (111)_{2}$ 7 = (\textbf{111})_2 is a $3$ -special integer.
$56 = (111000)_{2}$ 56 = (\textbf{111000})_2 is a $3$ -special integer.

000111 \oplus 111000111111

\begin{matrix} 000\textbf{111} \\ \oplus \\ \textbf{111}000 \\ \hline \textbf{111111} \end{matrix}

which stands for $1 + 2 + 2^{2} + 2^{3} + 2^{4} + 2^{5} = 63$ 1 + 2 + 2^2 + 2^3 + 2^4 + 2^5 = 63.

Scoring

Subtask $1$ ( $40$ points): $1 \leq n < 2^{20}; 1 \leq k \leq 20; 1 \leq t \leq 100$ 1 \le n < 2^{20}; 1 \le k \le 20; 1 \le t \le 100
Subtask $2$ ( $60$ points): $k = 1$ k = 1
Subtask $3$ ( $150$ points): No additional constraints