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

Эта задача про конфеты. Изначально у вас есть $$$1$$$ конфета, а вы хотите иметь ровно $$$n$$$ конфет.

Вы можете использовать два следующих заклинания в любом порядке не более $$$40$$$ раз суммарно.

  • Если у вас сейчас $$$x$$$ конфет, то, используя первое заклинание, можно превратить $$$x$$$ конфет в $$$2x-1$$$ конфету.
  • Если у вас сейчас $$$x$$$ конфет, то, используя второе заклинание, можно превратить $$$x$$$ конфет в $$$2x+1$$$ конфету.

Составьте список заклинаний так, чтобы после использования этих заклинаний по порядку у вас было ровно $$$n$$$ конфет, или определите, что это невозможно.

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

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

Каждый набор входных данных содержит одну строку с одним целым числом $$$n$$$ ($$$2 \le n \le 10^9$$$) — окончательным количеством конфет.

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

Для каждого набора входных данных выведите следующее.

Если есть возможность получить $$$n$$$ конфет, использовав заклинания не более $$$40$$$ раз, то в первой строке выведите одно целое число $$$m$$$ ($$$1 \le m \le 40$$$) — количество использованных вами заклинаний.

Затем во второй строке выведите $$$m$$$ целых чисел $$$a_{1}, a_{2}, \ldots, a_{m}$$$ ($$$a_{i}$$$ должно быть равно $$$1$$$ или $$$2$$$), разделенных пробелами. Если $$$a_{i} = 1$$$, это означает, что вы используете первое заклинание на $$$i$$$-м шаге. Если $$$a_{i} = 2$$$, это означает, что вы используете второе заклинание на $$$i$$$-м шаге.

Обратите внимание, что вам не нужно минимизировать количество операций $$$m$$$, и если есть несколько вариантов ответа, можно вывести любой.

Если ответа не существует, выведите $$$-1$$$.

Пример
Входные данные
4
2
3
7
17
Выходные данные
-1
1
2 
2
2 2 
4
2 1 1 1
Примечание

Для $$$n=3$$$ мы можем просто использовать второе заклинание один раз и получить $$$2 \cdot 1 + 1 = 3$$$ конфеты.

Для $$$n=7$$$ мы можем использовать второе заклинание дважды. Применив это один раз, мы получаем $$$3$$$ конфеты, а применив его дважды, мы получаем $$$2 \cdot 3 + 1 = 7$$$ конфет.