Phoenix has decided to become a scientist! He is currently investigating the growth of bacteria.

Initially, on day $1$, there is one bacterium with mass $1$.

Every day, some number of bacteria will split (possibly zero or all). When a bacterium of mass $m$ splits, it becomes two bacteria of mass $\frac{m}{2}$ each. For example, a bacterium of mass $3$ can split into two bacteria of mass $1.5$.

Also, every night, the mass of every bacteria will increase by one.

Phoenix is wondering if it is possible for the total mass of all the bacteria to be exactly $n$. If it is possible, he is interested in the way to obtain that mass using the minimum possible number of nights. Help him become the best scientist!


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains an integer $n$ ($2 \le n \le 10^9$) — the sum of bacteria masses that Phoenix is interested in. 


-----Output-----

For each test case, if there is no way for the bacteria to exactly achieve total mass $n$, print -1. Otherwise, print two lines.

The first line should contain an integer $d$  — the minimum number of nights needed.

The next line should contain $d$ integers, with the $i$-th integer representing the number of bacteria that should split on the $i$-th day.

If there are multiple solutions, print any.


-----Example-----
Input
3
9
11
2

Output
3
1 0 2 
3
1 1 2
1
0 


-----Note-----

In the first test case, the following process results in bacteria with total mass $9$:   Day $1$: The bacterium with mass $1$ splits. There are now two bacteria with mass $0.5$ each.  Night $1$: All bacteria's mass increases by one. There are now two bacteria with mass $1.5$.  Day $2$: None split.  Night $2$: There are now two bacteria with mass $2.5$.  Day $3$: Both bacteria split. There are now four bacteria with mass $1.25$.  Night $3$: There are now four bacteria with mass $2.25$.  The total mass is $2.25+2.25+2.25+2.25=9$. It can be proved that $3$ is the minimum number of nights needed. There are also other ways to obtain total mass 9 in 3 nights.

$ $

In the second test case, the following process results in bacteria with total mass $11$:   Day $1$: The bacterium with mass $1$ splits. There are now two bacteria with mass $0.5$.  Night $1$: There are now two bacteria with mass $1.5$.  Day $2$: One bacterium splits. There are now three bacteria with masses $0.75$, $0.75$, and $1.5$.  Night $2$: There are now three bacteria with masses $1.75$, $1.75$, and $2.5$.  Day $3$: The bacteria with mass $1.75$ and the bacteria with mass $2.5$ split. There are now five bacteria with masses $0.875$, $0.875$, $1.25$, $1.25$, and $1.75$.  Night $3$: There are now five bacteria with masses $1.875$, $1.875$, $2.25$, $2.25$, and $2.75$.  The total mass is $1.875+1.875+2.25+2.25+2.75=11$. It can be proved that $3$ is the minimum number of nights needed. There are also other ways to obtain total mass 11 in 3 nights.

$ $

In the third test case, the bacterium does not split on day $1$, and then grows to mass $2$ during night $1$.

Difficulty: interview

Starter code:

Solutions:
T = int(input())

for t in range(T):
  n = int(input())
  s = 1
  nxt = 2
  x = [1]
  while n > s:
    diff = n-s
    if diff <= nxt:
      x.append(diff)
      break
    x.append(nxt)
    s += nxt
    nxt *= 2
  x.sort()
  ans = ''
  for i in range(len(x)-1):
    v = x[i+1]-x[i]
    ans += str(v)+' '
  print(len(x)-1)
  print(ans[:-1])


import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: list(map(int, stdin.readline().split()))
nl = lambda: list(map(int, stdin.readline().split()))

def solve():
    n = ni()
    da = n.bit_length() - 1
    print(da)
    n -= da + 1
    f = [0]*da
    mx = 1
    for i in range(da):
        gr = min(mx, n//(da-i))
        f[i] = gr
        mx += gr
        n -= (da-i)*gr
    print(*f)


t = ni()
for _ in range(t):
    solve()


import sys
from collections import defaultdict
from copy import copy

R = lambda t = int: t(input())
RL = lambda t = int: [t(x) for x in input().split()]
RLL = lambda n, t = int: [RL(t) for _ in range(n)]

def solve():
  n = R()
  b = 1
  m = 1
  d = 0
  S = []
  while b < n:
    if b + 2 * m >= n:
      S += [n - b - m]
      m += n - b - m
      b += m
    else:
      if b + 4 * m > n:
        x = (n-b)//2 - m
        S += [x]
        m += x
      else:
        S += [m]
        m *= 2
      b += m
    d += 1
#  print(S,b)
  print(d)
  for c in S:
    print(c, end = " ")
  print()
  
T = R()
for _ in range(T):
  solve()


t = int(input())

for _ in range(t):
    w = int(input())
    res = []
    for i in range(300):
        if 2 ** (i + 1) - 1 > w:
            break
        res.append((2 ** i, 2 ** (i + 1) - 1))

    last_n, last_w = res[-1]
    if last_w != w:
        if last_w + last_n <= w:
            res.append((w - last_w, w))
        else:
            res = res[:-1]
            last_n, last_w = res[-1]

            necc = w - last_w - 2 * last_n
            ok = False
            n = last_n
            for x in range(min(necc // 2 + 1, n // 3 + 5), -1, -1):
                y = necc - 2 * x
                if 0 <= x and x <= n and 0 <= y and y <= n + x:
                    ok = True
                    res.append((last_n + x, last_w + last_n + x))
                    res.append((last_n + x + y, last_w + 2 * last_n + 2 * x + y))
                    break

            if not ok:
                exit(228)

    print(len(res) - 1)
    for i in range(len(res) - 1):
        print(res[i + 1][0] - res[i][0], end=' ')
    print()

n = int(input())
for i in range(int(n)):
    a = int(input())
    
    for j in range(35):
        if a <= 2**j - 1:
            print(j-1)
            break
    l = [2**x for x in range(j)]
    #print(l)
    
    total = sum(l)
    c = 1
    while total != a:
        try:
            l[-c] -= min(l[-c-1], total - a)
            total = sum(l)
            c += 1
            #print(c)
        except:
            pass
    ans = []
    for j in range(len(l) - 1):
        ans.append(l[j+1] - l[j])
    ans = [str(x) for x in ans]
    print(' '.join(ans))

t = int(input())

for _ in range(t):
    n = int(input())
    bacteria = 1
    tw = 1
    res = []
    while tw < n:
        rem = n - tw
        if bacteria > rem:
            print(1/0)
            break
        if rem - bacteria <= bacteria:
            new = rem - bacteria
        else:
            new = max(0, min(bacteria, rem - 3*bacteria))
        res.append(new)
        bacteria += new
        tw += bacteria
    print(len(res))
    print(*res)


import sys
input = sys.stdin.readline

from itertools import accumulate

PLUS=[1<<i for i in range(1,31)]
SUM=list(accumulate(PLUS))

t=int(input())
for tests in range(t):
    n=int(input())-1
    
    for i in range(30):
        if SUM[i]>=n:
            ANS=i+1
            break
    print(ANS)
    ALIST=[0]*ANS
    NOW=1
    n-=ANS
    
    for i in range(ANS):
        ALIST[i]=min(n//(ANS-i),NOW)
        n-=ALIST[i]*(ANS-i)
        NOW+=ALIST[i]
        #print(n,ALIST,NOW)
    print(*ALIST)



from collections import Counter
t = int(input())
for _ in range(t):
    n = int(input())
    if n == 8:
        print(3)
        print(1, 0, 1)
    elif n == 4:
        print(2)
        print(0, 1)
    else:
        b = n.bit_length()
        ans = [1 << i for i in range(b)]
        t = 0
        c = 0
        n = 2 ** b - 1 - n
        for i in range(1, b):
            if (n >> (b - i)) & 1:
                t += 1
                c += 1
            ans[i] -= t
            t *= 2
        ans[-1] -= (c + (n & 1))
        res = [0] * (b - 1)
        for i in range(b - 1):
            res[i] = ans[i + 1] - ans[i]
        print(b - 1)
        print(' '.join(map(str, res)))


t = int(input())

for _ in range(t):
	n = int(input())
	b, m = 1, 1
	res = []
	while True:
		if 2*b+m >= n:
			res.append(n - (m+b))
			break
		add = min(b, (n - (2*b+m)) // 2)
		res.append(add)
		b += add
		m += b
	d = len(res)
	print(d)
	print(" ".join(str(a) for a in res))

from collections import deque

def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


t = read_int()
for case_num in range(t):
    n = read_int()
    day = 0
    num = 1
    weight = 1
    history = []
    while weight < n:
        day += 1
        delta = n - weight
        if num <= delta <= 2 * num:
            history.append(delta - num)
            weight = n
        elif delta > 2 * num:
            history.append(num)
            num *= 2
            weight += num
        else:
            history.pop()
            k = min(delta // 2, num // 2)
            p = delta - 2 * k
            history.append(k)
            history.append(p)
            weight = n  
        if weight == n:
            break
    print(day)
    print(' '.join(map(str, history)))

import sys, random
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def main():
    inf = 10 ** 20

    t = int(input())
#    t, a, b = map(int, input().split())
#    t = 1
    
    for _ in range(1, t+1):
    #    print("Case #{}: ".format(_), end = '')
        n = int(input())
        
        total = 1
        plus = 1
        ans = []
        while(total != n):
            if(total + plus * 2 >= n):
                ans.append(n - total - plus)
                break
            else:
                next, l, r = -1, plus, plus << 1
                while(l <= r):
                    mid = (l + r) >> 1
                    if(total + mid * 2 > n):
                        r = mid - 1
                    else:
                        next = max(next, mid)
                        l = mid + 1
                ans.append(next - plus)
                plus = next
                total += plus
        print(len(ans))
        print(' '.join(map(str, ans)))
        
main()

T = int(input())
for case in range(T):
	n = int(input())
	#print("target",n)
	o = 0
	arr =  []
	while 2 ** o - 1 < n:
		arr.append(2 ** o)
		o += 1
	diff = 2 ** o -1 - n
	#print(arr)
	#print("min",o,"diff",diff)
	b = str(bin(diff))[2:][::-1]
	#print(b)
	o2 = 0
	arr2 =  []
	while o2 < len(b):
		if b[o2] == "0":
			pass
			#arr2.append(0) 
		else:
			arr2.append(2 ** o2)
		o2 += 1
	#print(arr,arr2)
	delta = len(arr) - len(arr2)
	for i in range(delta,len(arr2)+delta):
		arr[i] -= arr2[i-delta]
	#print(arr)
	ret = []
	for i in range(len(arr)-1):
		ret.append(str(arr[i+1]-arr[i]))
	days = len(ret)
	ret = " ".join(ret)
	print(days)
	print(ret)

		
	



		



import math

def __starting_point():
    t = int(input())
    for numtests in range(t):
        n = int(input())
        d = math.floor(math.log(n, 2))
        if n == 2:
            print("1")
            print("0")
        elif n == 3:
            print("1")
            print("1")
        else:
            print(str(d))
            for i in range(d-2):
                print(str(int(2**(i))), end = " ")
            if n < int(3*(2**(d-1))):
                print(str(math.floor((n+1-2**d)/2)), end = " ")
                print(str((n+1)%2))
            else:
                print(str(int(2**(d-2))), end = " ")
                print(str(int(n+1-3*(2**(d-1)))))
__starting_point()

import math

def process_test_case(i_test):
    n = int(input())
    n_days = math.floor(math.log2(n))

    out_list = []
    n_threshold = int(pow(2, n_days) + pow(2, n_days - 1) - 1)
    if n >= n_threshold:
        for i in range(n_days - 1):
            out_list.append(str(int(pow(2, i))))
        out_list.append(str(int(n - n_threshold)))
    else:
        for i in range(n_days - 2):
            out_list.append(str(int(pow(2, i))))
        n_reminder = n - pow(2, n_days) + 1
        a = n_reminder // 2
        b = n_reminder - 2 * a
        out_list.append(str(a))
        out_list.append(str(b))

    print(int(n_days))
    print(' '.join(out_list))


n_tests = int(input())
for i_test in range(1, n_tests + 1):
    process_test_case(i_test)


t=int(input())
for i in range(t):
    n=int(input())
    dig=0
    while 2**dig-1<n:
        dig+=1
    print(dig-1)
    D=dig-1
    num=1
    n-=1
    n-=D
    l=[0]*D
    for j in range(D):
        l[j]=min(num,n//(D-j))
        num+=l[j]
        n-=l[j]*(D-j)
    print(*l)