D. Феникс и наука
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Феникс решил стать ученым! Сейчас он изучает рост бактерий.

Изначально, в день $$$1$$$, есть одна бактерия массой $$$1$$$.

Каждый день некоторое количество бактерий делятся (возможно, все или ни одной). Когда бактерия массой $$$m$$$ делится, она превращается в две бактерии массой $$$\frac{m}{2}$$$ каждая. Например, бактерия массой $$$3$$$ может разделиться на две бактерии массой $$$1.5$$$.

Каждую ночь масса каждой бактерии увеличивается на один.

Феникса интересует вопрос: может ли общая масса бактерий стать в точности равна $$$n$$$. Если может, то его интересует как добиться такой массы за минимальное количество ночей. Помогите ему стать самым лучшим ученым!

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

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

В единственной строке каждого набора задано целое число $$$n$$$ ($$$2 \le n \le 10^9$$$) — суммарная масса бактерий, которой хочет добиться Феникс.

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

Для каждого набора входных данных, если не существует способа получить общую массу равную $$$n$$$, выведите -1. В противном случае, выведите две строки.

В первой строке выведите целое число $$$d$$$ — минимальное необходимое количество ночей.

В следующей строке выведите $$$d$$$ целых чисел, где $$$i$$$-е число обозначает количество бактерий, которые поделятся в $$$i$$$-й день.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
9
11
2
Выходные данные
3
1 0 2 
3
1 1 2
1
0
Примечание

В первом наборе, можно получить общую массу бактерий ровно $$$9$$$ следующим образом:

  • День $$$1$$$: Бактерия с массой $$$1$$$ делится. Получаем две бактерии с массой $$$0.5$$$.
  • Ночь $$$1$$$: Все бактерии увеличивают массу на один. Получаем две бактерии с массой $$$1.5$$$.
  • День $$$2$$$: Ни одна бактерия не делится.
  • Ночь $$$2$$$: Получаем две бактерии с массой $$$2.5$$$.
  • День $$$3$$$: Обе бактерии делятся. Получаем четыре бактерии с массой $$$1.25$$$.
  • Ночь $$$3$$$: Получаем четыре бактерии с массой $$$2.25$$$.
Суммарная масса равна $$$2.25+2.25+2.25+2.25=9$$$. Можно доказать, что $$$3$$$ — минимальное необходимое количество ночей. Есть и другие способы добиться суммарной массы 9 за 3 ночи.

$$$ $$$

В втором наборе, можно получить общую массу бактерий ровно $$$11$$$ следующим образом:

  • День $$$1$$$: Бактерия с массой $$$1$$$ делится. Получаем две бактерии с массой $$$0.5$$$.
  • Ночь $$$1$$$: Получаем две бактерии с массой $$$1.5$$$.
  • День $$$2$$$: Одна бактерия делится. Получаем три бактерии с массами $$$0.75$$$, $$$0.75$$$ и $$$1.5$$$.
  • Ночь $$$2$$$: Получаем три бактерии с массами $$$1.75$$$, $$$1.75$$$ и $$$2.5$$$.
  • День $$$3$$$: Бактерия с массой $$$1.75$$$ и бактерия с массой $$$2.5$$$ делятся. Получаем пять бактерий с массами $$$0.875$$$, $$$0.875$$$, $$$1.25$$$, $$$1.25$$$ и $$$1.75$$$.
  • Ночь $$$3$$$: Получаем пять бактерий с массами $$$1.875$$$, $$$1.875$$$, $$$2.25$$$, $$$2.25$$$ и $$$2.75$$$.
Суммарная масса равна $$$1.875+1.875+2.25+2.25+2.75=11$$$. Можно доказать, что $$$3$$$ — минимальное необходимое количество ночей. Есть и другие способы добиться суммарной массы 11 за 3 ночи.

$$$ $$$

Во третьем наборе, бактерия не делится в день $$$1$$$, а потом увеличивает массу до $$$2$$$ в ночь $$$1$$$.