B. Бинарная покраска
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано натуральное число $$$x$$$. Найдите любую последовательность чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ такую, что:

  • $$$1 \le n \le 32$$$,
  • $$$a_i$$$ равно $$$1$$$, $$$0$$$ или $$$-1$$$ для всех $$$0 \le i \le n - 1$$$,
  • $$$x = \displaystyle{\sum_{i=0}^{n - 1}{a_i \cdot 2^i}}$$$,
  • Не существует $$$0 \le i \le n - 2$$$ такого, что $$$a_{i} \neq 0$$$ и $$$a_{i + 1} \neq 0$$$.

Можно доказать, что под ограничениями задачи всегда существует как минимум одна подходящая последовательность.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$x$$$ ($$$1 \le x < 2^{30}$$$).

Выходные данные

Для каждого набора входных данных на первой строке выведите число $$$n$$$ ($$$1 \le n \le 32$$$) — длину последовательности $$$a_0, a_1, \ldots, a_{n-1}$$$.

На следующей строке выведите саму последовательность $$$a_0, a_1, \ldots, a_{n-1}$$$.

Если подходящих последовательностей несколько, вы можете вывести любую из них.

Пример
Входные данные
7
1
14
24
15
27
11
19
Выходные данные
1
1
5
0 -1 0 0 1
6
0 0 0 -1 0 1
5
-1 0 0 0 1
6
-1 0 -1 0 0 1
5
-1 0 -1 0 1
5
-1 0 1 0 1
Примечание

В первом наборе входных данных, одной из подходящих последовательностей является $$$[1]$$$, так как $$$(1) \cdot 2^0 = 1$$$.

Во втором наборе входных данных, одной из подходящих последовательностей является $$$[0,-1,0,0,1]$$$, так как $$$(0) \cdot 2^0 + (-1) \cdot 2^1 + (0) \cdot 2^2 + (0) \cdot 2^3 + (1) \cdot 2^4 = -2 + 16 = 14$$$.