Problem C
Easy Multiplication

Stock photo by Tatiana Maramygina used under license.

Members of the Modern Arithmetic Puzzle Society (MAPS) love to multiply numbers together using long multiplication. One of the members of MAPS, Molly, observed that multiplying two integers in this way is much easier when their base-$b$ representations have few nonzero digits. Molly came up with an approach to try to take advantage of this observation when multiplying arbitrary pairs of positive integers. She explains her method as follows:

• For any positive integer, $p$, define $c_ b(p)$ to be the number of nonzero digits in the base-$b$ representation of $p$.

• To multiply positive integers $m$ and $n$, perform the following steps:

  1. Find the smallest positive integer, $k$, that minimizes $c_ b(km)$.

  2. Find the smallest positive integer, $\ell $, that minimizes $c_ b(\ell n)$.

  3. Using long multiplication, multiply $km$ by $\ell n$ to get $r$.

  4. Divide $r$ by $k$ to get $s$.

  5. Divide $s$ by $\ell $ to get the final answer.

Molly thinks that there is some promise in her new approach, but she is having trouble with the first two steps in her method. Can you help her? As a starting point, she wants to see how this will work for the simplest case: base $2$.

Input

The first line of input contains an integer, $N$, the number of test cases ($1 \leq N \leq 20$). Each of the next $N$ lines contains a single integer, $m$, where $1 \leq m \leq 100\, 000$.

Output

For each test case, $m$, output a line containing the indices of the $1$-bits in the product $km$, in ascending order and separated by spaces, where $k$ is the smallest positive integer that minimizes $c_2(km)$. Bits are indexed starting from $0$, with index $0$ corresponding to the least significant bit. For example, the $1$-bits in the number $13$ have indices $0$, $2$, and $3$.

3
6
11
42

1 2
0 5
1 3 5