Consider an array A = \{a_{1}, a_{2},...,a_{n}\} of size n ≥ 1. If a_{k} = 2^{x} -1 for all  1≤ k ≤ n,  for some integer x (1 ≤ x ≤ 60), then A is called interesting array.

You are given a number C. Find any interesting array A of minimum possible size such that  a_{1} \bigoplus a_{2} \bigoplus...\bigoplus a_{n} = C, where \bigoplus represents bitwise XOR operation.

If there exists multiple such arrays, output any one.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains single integer C on a single line.

------ Output Format ------ 

- For each testcase, on the first line output the minimum possible size of array A satisfying the given property.
- On the next line output the elements of array A in any order. 

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$0 ≤ C < 2^{60}$
- It is guaranteed in the input that sum of lengths of arrays over all testcases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
1
1
2
1 3
1
3

----- explanation 1 ------ 
$\textbf{Test case}$ 1: $C=1$, $A$ can be $\{1\}$

$\textbf{Test case}$ 2: $C=2$, $A$ can be $\{1,3\}$

$\textbf{Test case}$ 3: $C=3$, $A$ can be $\{3\}$

Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Mathematics

Data structures

Ad-hoc
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	C = int(input())
	if C == 0:
		print('2\n1 1\n')
		continue
	b = ''
	while C > 0:
		b += str(C % 2)
		C = C // 2
	b = b[::-1]
	size = len(b)
	v = []
	prev = b[0]
	v.append(2 ** size - 1)
	for i in range(1, size):
		if b[i] == prev:
			continue
		v.append(2 ** (size - i) - 1)
		prev = b[i]
	print(len(v))
	print(' '.join(map(str, v)))


t = int(input())

def solve():
	C = int(input())
	if C == 0:
		print(2)
		print(1, 1)
		return
	xor = 0
	ans = []
	for i in range(60, -1, -1):
		if C & 1 << i:
			if xor & 1 << i:
				continue
			else:
				ans.append((1 << i + 1) - 1)
				xor ^= (1 << i + 1) - 1
		elif not xor & 1 << i:
			continue
		else:
			ans.append((1 << i + 1) - 1)
			xor ^= (1 << i + 1) - 1
	print(len(ans))
	if ans:
		print(*ans)
	else:
		print(0)
while t:
	solve()
	t -= 1


def func(n):
	c = 0
	x = 1
	for _ in range(n):
		c += x
		x *= 2
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 0:
		print(2)
		print(1, 1)
		continue
	l = []
	flag = n % 2
	n = n >> 1
	c = 1
	while n != 0:
		x = n % 2
		n = n >> 1
		if x != flag:
			l.append(c)
			flag = x
		c += 1
	l.append(c)
	print(len(l))
	for i in l:
		print(func(i), end=' ')
	print()


t = int(input())
for _ in range(t):
	c = int(input())
	temp = c
	arr = []
	n = 0
	while c > 0:
		arr.append(c % 2)
		c //= 2
		n += 1
	flip = 0
	ini = 2 ** n - 1
	ans = [ini]
	for i in range(n - 1, -1, -1):
		if arr[i] == 0 and flip == 0:
			ans.append(2 ** (i + 1) - 1)
			flip = 1
		if arr[i] == 1 and flip == 1:
			ans.append(2 ** (i + 1) - 1)
			flip = 0
	if temp == 0:
		print(2)
		print(1, 1)
	else:
		print(len(ans))
		for i in ans:
			print(i, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	x = bin(n)[2:]
	temp = '1'
	l = [2 ** len(x) - 1]
	for i in range(1, len(x)):
		if x[i] != temp:
			l.append(2 ** (len(x) - i) - 1)
			if temp == '1':
				temp = '0'
			else:
				temp = '1'
	if n == 0:
		print(2)
		print(1, 1)
	else:
		print(len(l))
		print(*l)


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
lx = lambda x: map(int, input().split(x))
yy = lambda : print('YES')
nn = lambda : print('NO')
from math import log10, log2, ceil, factorial as fac, gcd, inf, sqrt, log
from bisect import bisect_right as br, bisect_left as bl, insort
from collections import Counter
mod = 10 ** 9 + 7

def Nprime(n):
	if n == 2 or n == 3:
		return 0
	if n == 1:
		return 1
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 1
		i += 1
	return 0

def g(n):
	i = 2
	(od, ev) = (0, 0)
	x = n
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
				if i % 2:
					od += 1
				else:
					ev += 1
		i += 1
	if n > 1:
		if n % 2:
			od += 1
		else:
			ev += 1
	return (od, ev)
for _ in range(t()):
	c = t()
	if c == 0:
		print(2)
		print(1, 1)
		continue
	x = c
	l = []
	while 1:
		p = bin(x)[2:]
		temp = int('1' * len(p), 2)
		l.append(temp)
		if log2(x + 1).is_integer():
			break
		x = x ^ temp
	print(len(l))
	print(*l)


import bisect
l = [(1 << x) - 1 for x in range(61)]
for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print(2)
		print(3, 3)
	elif n in l:
		print(1)
		print(n)
	else:
		cnt = 0
		ans = []
		while n not in l:
			cnt += 1
			ind = bisect.bisect_left(l, n)
			ans.append(l[ind])
			n = l[ind] - n
		cnt += 1
		ans.append(n)
		print(cnt)
		print(*ans)


def check(c):
	if c == 0:
		return [1, 1]
	a = []
	data = bin(c)[2:]
	p_val = '1'
	a.append(2 ** len(data) - 1)
	for i in range(len(data)):
		if p_val != data[i]:
			a.append(2 ** len(data[i:]) - 1)
			p_val = data[i]
	return a
t = int(input())
for _ in range(t):
	c = int(input())
	sharma = check(c)
	print(len(sharma))
	print(*sharma)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 0:
		print(2)
		print(1, 1)
	else:
		bc = 0
		binary = ''
		while n != 0:
			if n % 2 == 0:
				binary = '0' + binary
			else:
				binary = '1' + binary
			bc += 1
			n //= 2
		l = []
		l.append(2 ** bc - 1)
		bc = 2 ** (bc - 1)
		i = 1
		b = '1'
		while i < len(binary):
			if binary[i] != b:
				l.append(bc - 1)
				if b == '1':
					b = '0'
				else:
					b = '1'
			i += 1
			bc //= 2
		print(len(l))
		print(*l)


from sys import stdin
inp = stdin.readline
interesting = list((2 ** p - 1 for p in range(60 + 1)))
T = int(inp())
ans = []
for tx in range(T):
	C = int(inp())
	if C == 0:
		A = [1, 1]
	else:
		A = []
	hi = len(interesting)
	while C:
		lo = 0
		while hi - lo > 1:
			md = (hi + lo) // 2
			if interesting[md] < C:
				lo = md
			else:
				hi = md
		A.append(interesting[hi])
		C ^= interesting[hi]
	ans.append(len(A))
	ans.append(' '.join(map(str, A)))
print(*ans, sep='\n')


for _ in range(int(input())):
	c = int(input())
	if c == 0:
		print(2)
		print('1 1')
		continue
	s = bin(c).replace('0b', '')
	l = []
	n = len(s)
	x = 1
	for i in range(n):
		if int(s[i]) == x:
			l.append(n - i)
			x = not x
	print(len(l))
	for i in l:
		print(2 ** i - 1, end=' ')
	print()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	c = int(input())
	if c == 0:
		print(2)
		print(1, 1)
	else:
		b = bin(c)[2:][::-1]
		ex = []
		for i in range(len(b)):
			if b[i] == '1':
				if i - 1 >= 0 and b[i - 1] == '1':
					ex.pop()
					ex.append(2 ** (i + 1) - 1)
				else:
					if i != 0:
						ex.append(2 ** i - 1)
					ex.append(2 ** (i + 1) - 1)
		print(len(ex))
		print(*ex)


for _ in range(int(input())):
	C = int(input())
	if C == 0:
		print(2)
		print(1, 1)
	else:
		c = bin(C)[2:]
		flag = '1'
		lis = []
		lis.append(int('1' * len(c), 2))
		for i in range(1, len(c)):
			if flag != c[i]:
				lent = len(c) - i
				lis.append(int('1' * lent, 2))
				flag = str(1 - int(flag))
		print(len(lis))
		for i in range(len(lis)):
			print(lis[i], end=' ')
		print()


ans = ''
for _ in range(int(input())):
	n = int(input())
	if n == 0:
		ans += '2\n1 1\n'
		continue
	if n + 1 & n == 0:
		ans += str(1) + '\n' + str(n) + '\n'
		continue
	num = bin(n)[2:]
	l = len(num)
	res = []
	cnt = 1
	for i in range(len(num)):
		if num[i] == '1' and cnt % 2 != 0:
			res.append(int('1' * (l - i), 2))
			cnt += 1
		elif num[i] == '0' and cnt % 2 == 0:
			res.append(int('1' * (l - i), 2))
			cnt += 1
		elif num[i] == '0' and cnt % 2 != 0:
			continue
		elif num[i] == '1' and cnt % 2 == 0:
			continue
	ans += str(len(res)) + '\n'
	for i in res:
		ans += str(i) + ' '
	ans += '\n'
print(ans)


for _ in range(int(input())):
	n = int(input())
	if n != 0:
		n = bin(n)[2:]
		l = len(n)
		s = ''
		k = 0
		for i in range(l):
			if n[i] == '1':
				if k % 2 == 0:
					s += f'{2 ** (l - i) - 1} '
					k += 1
			elif k % 2:
				s += f'{2 ** (l - i) - 1} '
				k += 1
		print(k)
		print(s)
	else:
		print(2)
		print(1, 1)


from math import floor, log

def get_range(c):
	return floor(log(c, 2)) + 1

def solve(c):
	arr = []
	pow = 60
	prefix = 0
	while pow >= 0:
		bit1 = 1 << pow & prefix
		bit2 = 1 << pow & c
		if bit1 != bit2:
			prefix ^= (1 << pow + 1) - 1
			arr.append((1 << pow + 1) - 1)
		pow -= 1
	if arr == []:
		return (2, [7, 7])
	return (len(arr), arr)
for _ in range(int(input())):
	(n, arr) = solve(int(input()))
	print(n)
	print(' '.join(map(str, arr)))


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 0:
		print(2)
		print(1, 1, sep=' ')
	else:
		k = 0
		temp = n
		while temp // 2 != 0:
			temp //= 2
			k += 1
		xor = 0
		array = []
		count = 0
		while k >= 0:
			if 1 << k & n != 1 << k & xor:
				count += 1
				xor ^= (1 << k + 1) - 1
				array.append((1 << k + 1) - 1)
			k -= 1
		print(count)
		for i in range(-1, -(len(array) + 1), -1):
			print(array[i], end=' ')
		print()


for t in range(int(input())):
	c = int(input())
	x = 0
	a = []
	for i in range(59, -1, -1):
		y = c & 1 << i
		z = x & 1 << i
		if y != z:
			k = 2 ** (i + 1) - 1
			a.append(k)
			x ^= k
	if c == 0:
		a.append(1)
		a.append(1)
	print(len(a))
	print(*a)


import collections
import math

def nice(n):
	ans = []
	if n == 0:
		print(2)
		print(1, 1)
		return
	diff = float('inf')
	while diff > 0:
		cnt = math.floor(math.log2(n))
		hp = 2 ** (cnt + 1) - 1
		ans.append(hp)
		diff = hp - n
		n = diff
	print(len(ans))
	for i in ans:
		print(i, end=' ')
	print('\r')
t = int(input())
for i in range(t):
	n = int(input())
	nice(n)


import math
for _ in range(int(input())):
	C = int(input())
	A = []
	curr = 0
	if C == 0:
		print(2)
		print(1, 1)
	else:
		A = bin(C)[2:]
		ans = []
		num = 0
		for i in range(len(A)):
			if int(A[i]) != num:
				ans.append(2 ** (len(A) - i) - 1)
				num = 1 - num
		ans.reverse()
		print(len(ans))
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


for _ in range(int(input())):
	c = int(input())
	if c == 0:
		print(2)
		print(1, 1)
	else:
		p = bin(c).replace('0b', '')
		k = len(p)
		l = []
		sel = 0
		for i in range(k):
			if sel % 2 == 0 and p[i] == '0':
				continue
			elif sel % 2 == 1 and p[i] == '0':
				l.append(pow(2, k - i) - 1)
				sel += 1
			elif sel % 2 == 0 and p[i] == '1':
				l.append(pow(2, k - i) - 1)
				sel += 1
			elif sel % 2 == 1 and p[i] == '1':
				continue
		l = l[::-1]
		print(sel)
		for i in l:
			print(i, end=' ')
		print()


def func():
	ans = []
	curr = 0
	for i in range(60, -1, -1):
		b1 = 1 << i & curr
		b2 = 1 << i & c
		if b1 != b2:
			ans.append((1 << i + 1) - 1)
			curr ^= (1 << i + 1) - 1
	if not ans:
		ans = [3, 3]
	print(len(ans))
	print(*ans)
for _ in range(int(input())):
	c = int(input())
	func()


powers = [1]
for i in range(1, 61):
	powers.append(powers[-1] * 2)
for i in range(61):
	powers[i] -= 1
for _ in range(int(input())):
	c = int(input())
	if c == 0:
		print('2\n1 1\n')
	else:
		cbin = bin(c)[2:]
		ans = [powers[len(cbin)]]
		for i in range(1, len(cbin)):
			if cbin[i] != cbin[i - 1]:
				ans.append(powers[len(cbin) - i])
		print(len(ans))
		print(*ans)


for _ in range(int(input())):
	c = int(input())
	s = bin(c)[2:]
	q = 2 ** len(s) - 1
	a = [q]
	(i, k, b) = (0, q, bin(q)[2:])
	while i < len(s):
		if s[i] != b[i]:
			v = 2 ** (len(s) - i) - 1
			a.append(v)
			k = k ^ v
			b = bin(k)[2:]
			if k == c:
				break
		i += 1
	print(len(a))
	print(*a, sep=' ')


t = int(input())
for i in range(t):
	c = int(input())
	res = []
	q = 0
	for j in range(60, -1, -1):
		bit1 = 1 << j & c
		bit2 = 1 << j & q
		if bit1 != bit2:
			res.append((1 << j + 1) - 1)
			q = q ^ res[-1]
	if len(res) == 0:
		print(2)
		print(' '.join(['1', '1']))
	else:
		print(len(res))
		print(' '.join([str(k) for k in res]))


def run_case():
	n = int(input())
	if n == 0:
		print('2')
		print('1 1')
		return
	ans = []
	while n > 0:
		ans.append(n % 2)
		n = n // 2
	res = []
	num = 0
	ans.reverse()
	for i in range(len(ans)):
		if ans[i] != num:
			res.append(2 ** (len(ans) - i) - 1)
			num = 1 - num
	print(len(res))
	for i in res:
		print(i, end=' ')
	print('')
t = int(input())
for i in range(t):
	run_case()


import math
t = int(input())
for _ in range(t):
	c = int(input())
	if c == 0:
		print('2')
		print('1', end=' ')
		print('1')
		continue
	arr = []
	while c > 0:
		x = math.floor(math.log(c, 2)) + 1
		y = 2 ** x - 1
		arr.append(y)
		c = y - c
	n = len(arr)
	print(n)
	for i in range(n):
		print(arr[i], end=' ')
	print()


import sys
from collections import defaultdict

def take_input():
	return sys.stdin.readline()

def print_arr(arr):
	sys.stdout.write(' '.join(map(str, arr)) + '\n')

def print_num(num):
	sys.stdout.write(str(num) + '\n')

def solve(test):
	target = int(input())
	curr_xor = 0
	ans = []
	for i in range(60, -1, -1):
		req_bit = 1 << i & target
		curr_bit = 1 << i & curr_xor
		if req_bit != curr_bit:
			nex_pow = (1 << i + 1) - 1
			curr_xor = curr_xor ^ nex_pow
			ans.append(nex_pow)
	if len(ans) == 0:
		ans.append(1)
		ans.append(1)
	print(len(ans))
	print(' '.join((str(ch) for ch in ans)))

def main():
	test_case = int(input())
	for t in range(test_case):
		solve(t)
main()


import math, heapq, bisect
from collections import Counter, deque, defaultdict

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	n = getInt()
	bl = n.bit_length()
	(v, ans, cur) = (int('1' * bl if bl > 0 else '0', 2), [], 0)
	for i in range(bl):
		if n & 1 << bl - i - 1 != cur & 1 << bl - i - 1:
			ans.append(v)
			cur ^= v
		v >>= 1
	if len(ans) == 0:
		ans = [1, 1]
	print(len(ans))
	print(*ans)

def ts(n, pr=False):
	if pr:
		for _ in range(n):
			print(solve())
	else:
		for _ in range(n):
			solve()
ts(getInt())


from math import log2
for _ in range(int(input())):
	n = int(input())
	c = 0
	a = []
	if n == 0:
		print(2)
		print(1, 1)
		continue
	for i in range(60, -1, -1):
		if n & 1 << i != c & 1 << i:
			k = 2 ** (i + 1) - 1
			a.append(k)
			c = c ^ k
	print(len(a))
	for i in a:
		print(i, end=' ')
	print()


def solve3():
	n = int(input())
	p = bin(n)[2:]
	if n == 0:
		print(2)
		print('1 1')
		return
	l = len(p)
	ans = []
	cur = 0
	for i in range(len(p)):
		if int(p[i]) != cur:
			cur = 1 - cur
			ans.append(2 ** (l - i) - 1)
	print(len(ans))
	print(*ans)
for testis in range(int(input())):
	solve3()


for _ in range(int(input())):
	n = int(input())
	l = bin(n)[2:]
	l = list(l)
	fac = 0
	ans = []
	for i in range(len(l)):
		if l[i] == '1':
			if fac == 0:
				ans.append(pow(2, len(l) - i) - 1)
			fac = 1
		if l[i] == '0':
			if fac == 1:
				ans.append(pow(2, len(l) - i) - 1)
			fac = 0
	if n == 0:
		ans = [1, 1]
	print(len(ans))
	for i in ans:
		print(i, end=' ')
	print()


for test in range(int(input())):
	n = int(input())
	if n == 0:
		print(2)
		print(1, 1)
		continue
	bits = bin(n)[2:]
	k = len(bits)
	l = []
	c = 0
	xor_value = 0
	for i in range(k):
		if bits[i] == '1':
			if c % 2 == 0:
				l.append(2 ** (k - i) - 1)
				c += 1
		elif c % 2 == 1:
			l.append(2 ** (k - i) - 1)
			c += 1
	print(c)
	print(*l)
	for i in l:
		xor_value ^= i
	if xor_value != n:
		print(1 / 0)


def binp(n):
	return bin(n).replace('0b', '')
for t in range(int(input())):
	c = int(input())
	t = str(binp(c))
	n = len(t)
	a = 0
	l = []
	for i in range(n):
		if a % 2 == 0:
			if int(t[i]) == 1:
				l.append(2 ** (n - i) - 1)
				a = a + 1
		if a % 2 != 0:
			if int(t[i]) == 0:
				l.append(2 ** (n - i) - 1)
				a = a + 1
	if a != 0:
		print(a)
		for i in range(a - 1):
			print(l[i], end=' ')
		print(l[a - 1])
	else:
		print(2)
		print(1, 1)


x = int(input())
for i in range(x):
	y = int(input())
	a = []
	if y == 0:
		print(2)
		print('1 1')
		continue
	while y > 0:
		if y & 1 == 0:
			a.append(0)
		else:
			a.append(1)
		y = y >> 1
	count = 1
	for jj in range(len(a) - 1):
		if a[jj] != a[jj + 1]:
			count += 1
	b = []
	b.append(str(2 ** len(a) - 1))
	for kk in range(len(a) - 1, 0, -1):
		if a[kk] != a[kk - 1]:
			b.append(str(2 ** kk - 1))
	ans = ' '
	print(count)
	print(ans.join(b))


for i in range(int(input())):
	n = int(input())
	if n == 0:
		(an, a) = (2, [1, 1])
	else:
		x = bin(n)[2:]
		(an, a, n) = (0, [], len(x))
		for i in range(n):
			if int(x[i]) and (not an & 1) or (not int(x[i]) and an & 1):
				a.append((1 << n - i) - 1)
				an += 1
	print(an)
	print(*a)


m = 1 << 60
for t in range(int(input())):
	c = int(input().strip())
	b = 1
	pb = c & b
	v = 0
	n = 1
	res = []
	if c == 0:
		res = ['1', '1']
		n = 2
	else:
		while c > 0:
			b = c & 1
			if pb != b:
				n += 1
				res.append(str(v))
			pb = b
			v = (v << 1) + 1
			c >>= 1
		res.append(str(v))
	print(n)
	print(' '.join(res))


def MinimizeTheSize2():
	num_test_cases = int(input())
	for _ in range(num_test_cases):
		target = int(input())
		if target == 0:
			print(2)
			print('1 1')
			continue
		target_bits = [int(x) for x in bin(target)[2:]]
		are_there_an_even_number_of_set_bits = 1
		full = 2 ** len(target_bits) - 1
		ans = []
		for (i, target_bit) in enumerate(target_bits):
			if target_bit == are_there_an_even_number_of_set_bits:
				ans += [full >> i]
				are_there_an_even_number_of_set_bits ^= 1
		print(len(ans))
		print(*ans, sep=' ')
	return
MinimizeTheSize2()


lookup = []
y = 2
for j in range(1, 20):
	lookup.append(y - 1)
	y = y * 2
T = int(input())
for tc in range(T):
	C = int(input())
	nbits = len(bin(C)[2:])
	cur = C
	mylist = []
	while cur > 0:
		cur = cur ^ 2 ** nbits - 1
		mylist.append(2 ** nbits - 1)
		x = cur
		nbits = len(bin(cur)[2:])
	if C == 0:
		mylist.append(1)
		mylist.append(1)
	mylist.sort()
	print(len(mylist))
	for x in mylist:
		print(x, end=' ')
	print()


import sys
l = []
x = 2
for i in range(1, 61):
	l.append(x - 1)
	x = x * 2
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	if n == 0:
		print(2)
		print(1, 1)
	else:
		x = bin(n)[2:]
		z = len(x)
		a = 0
		g = [l[z - 1]]
		v = '1'
		for i in range(1, z):
			if x[i] == v:
				continue
			else:
				a = a + 1
				v = x[i]
				g.append(l[z - i - 1])
		print(a + 1)
		print(*g)


t = int(input())
for i in range(t):
	a = bin(int(input()))[2:]
	if a == '0':
		print(2)
		lst = [1, 1]
	else:
		lst = [2 ** len(a) - 1]
		for j in range(1, len(a)):
			if a[j] != a[j - 1]:
				lst.append(2 ** (len(a) - j) - 1)
		print(len(lst))
		lst = set(lst)
	print(*list(lst))


for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print(2)
		print('1 1')
		continue
	s = ''
	while n > 0:
		s += str(n % 2)
		n //= 2
	s = s[::-1]
	n = len(s)
	st = []
	st.append(pow(2, n) - 1)
	ch = '1'
	for i in range(0, n):
		if s[i] != ch:
			st.append(pow(2, n - i) - 1)
			ch = s[i]
	print(len(st))
	print(*st[::-1])


nums = [(1 << i) - 1 for i in range(1, 61)]
for _ in range(int(input())):
	c = int(input())
	if c == 0:
		print(2)
		print(1, 1)
		continue
	res = []
	j = c.bit_length()
	j -= 1
	res.append(nums[j])
	while j >= 0:
		jbit = c & 1 << j
		while j >= 0 and (c & 1 << j == jbit == 0 or (c & 1 << j and jbit)):
			j -= 1
		if j >= 0:
			res.append(nums[j])
	print(len(res))
	print(*res)


import sys
for _ in range(int(input())):
	n = int(sys.stdin.readline())
	c = 0
	ans = []
	f = 0
	c = 0
	if n == 0:
		sys.stdout.write('2\n')
		sys.stdout.write('1 1\n')
	else:
		for i in range(61, -1, -1):
			if n & 1 << i:
				if c % 2 == 0:
					ans.append((1 << i + 1) - 1)
					c += 1
			else:
				f = 0
				if c % 2:
					ans.append((1 << i + 1) - 1)
					c += 1
		sys.stdout.write(str(len(ans)) + '\n')
		for i in ans:
			sys.stdout.write(str(i) + ' ')
		sys.stdout.write('\n')


from collections import deque
import bisect
t = int(input())
a = [0 for x in range(64)]
a[0] = 1
k = 1
h = 1
while h < 64:
	a[h] = 2 * k - 1
	k *= 2
	h += 1
s = set(a)
while t > 0:
	c = int(input())
	n = 0
	d = deque()
	while c not in s:
		u = bisect.bisect_right(a, c)
		d.insert(0, a[u])
		c = a[u] - c
		n += 1
	d.insert(0, c)
	n += 1
	print(n)
	for x in d:
		print(x, end=' ')
	print()
	t -= 1


import math
t = int(input())
for _ in range(t):
	c = int(input())
	ans = []
	if c == 0:
		print(2)
		print('1 1')
		continue
	while c > 0:
		f = math.ceil(math.log2(c) + 1e-14)
		x = 2 ** f - 1
		c = x - c
		ans.append(x)
	print(len(ans))
	for i in ans:
		print(i, end=' ')
	print()


def isSet(n, i):
	if n & 1 << i:
		True
	else:
		False
for _ in range(int(input())):
	n = int(input())
	s = '0' + bin(n).replace('0b', '')
	if n == 0:
		print(2)
		print(1, 1)
		continue
	k = len(s)
	ans = []
	for i in range(1, k):
		if s[i] != s[i - 1]:
			ans.append(2 ** (k - i) - 1)
	print(len(ans))
	print(*ans)


for vcbhnj in range(int(input())):
	c = int(input())
	if c == 0:
		print(2)
		print(2 ** 60 - 1, 2 ** 60 - 1)
		continue
	x = bin(c)[2:]
	a = [[0, int(x[0])]]
	for i in range(1, len(x)):
		if x[i] != x[i - 1]:
			a.append([i, int(x[i])])
	n = len(a)
	ans = []
	for i in a:
		ans.append(2 ** (len(x) - i[0]) - 1)
	print(n)
	for i in ans:
		print(i, end=' ')
	print()


for x in range(int(input())):
	n = int(input())
	if n == 0:
		print(2)
		print(*[1, 1])
	else:
		a = bin(n)
		b = a[2:]
		l = []
		c = 0
		for i in range(len(b)):
			if b[i] == '1':
				if not c & 1:
					l.append((1 << len(b) - i) - 1)
					c = c + 1
			elif c & 1:
				l.append((1 << len(b) - i) - 1)
				c = c + 1
		print(c)
		print(*l)


T = int(input())
for i in range(T):
	C = int(input())
	if C == 0:
		print(2)
		print('1 1')
	else:
		y = 1
		xp = 1 if C & 1 == 1 else 0
		C = C >> 1
		p = []
		while C != 0:
			x = 1 if C & 1 == 1 else 0
			if x != xp:
				p.append(y)
			xp = x
			y = y << 1 | 1
			C = C >> 1
		p.append(y)
		print(len(p))
		for x in p:
			print(x, end=' ')
		print('\r')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	c = int(input())
	if c == 0:
		print(2)
		print(1)
		print(1)
	elif c & c + 1 == 0:
		print(1)
		print(c)
	else:
		temp = bin(c).replace('0b', '')
		temp = '0' * (60 - len(temp)) + temp
		set_bit = [0] * 60
		ans = []
		one = 0
		for i in range(60):
			set_bit[i] = one
			if temp[i] == '1' and set_bit[i] % 2 == 0:
				one += 1
				set_bit[i] += 1
			elif temp[i] == '0' and set_bit[i] % 2 != 0:
				one += 1
				set_bit[i] += 1
		one = 0
		for i in range(60):
			set_bit[i] -= one
			if set_bit[i] != 0:
				one += 1
				ans.append((1 << 60 - i) - 1)
				set_bit[i] -= 1
		print(len(ans))
		print(*ans)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	if n == 0:
		print(2)
		print(1, 1)
		continue
	ar = []
	t1 = n
	while t1:
		if t1 % 2 == 0:
			ar.append(0)
		else:
			ar.append(1)
		t1 = t1 // 2
	itr1 = len(ar)
	res = []
	res.append((1 << itr1) - 1)
	itr1 = itr1 - 1
	while itr1 >= 0:
		if ar[itr1] == 1:
			itr1 = itr1 - 1
		else:
			prev = itr1
			while itr1 >= 0 and ar[itr1] == 0:
				itr1 = itr1 - 1
			res.append((1 << prev + 1) - 1)
			if itr1 > -1:
				res.append((1 << itr1 + 1) - 1)
	print(len(res))
	print(*res)


def solve(c):
	if c == 0:
		print(2)
		print('1 1')
		return
	cb = '{0:b}'.format(c)
	ans = []
	l = len(cb)
	so_far = 0
	for b in range(0, len(cb)):
		if cb[b] == '1':
			if so_far % 2 == 1:
				l -= 1
				continue
			ans.append((1 << l) - 1)
			so_far += 1
			l -= 1
			continue
		if so_far % 2 == 0:
			l -= 1
			continue
		ans.append((1 << l) - 1)
		so_far += 1
		l -= 1
	print(len(ans))
	print(*ans)
t = int(input().strip())
inputs = []
for _ in range(t):
	inputs.append(int(input().strip()))
for c in inputs:
	solve(c)


def decimalToBinary(n):
	return bin(n).replace('0b', '')
T = int(input())
for _ in range(T):
	ret = []
	C = int(input())
	if C == 0:
		print(2)
		print(1, 1)
		continue
	C_str = str(decimalToBinary(C))
	curr = 0
	n = len(C_str)
	for (i, x) in enumerate(C_str):
		if int(x) != curr:
			ret.append(int('1' * (n - i), 2))
			curr = (curr + 1) % 2
	print(len(ret))
	print(*ret)


test = []
for i in range(1, 61):
	test.append(str((1 << i) - 1))
t = int(input())
for z in range(t):
	c = int(input())
	if c == 0:
		print(2)
		print('1 1')
		continue
	res = []
	i = 1
	cur = c & 1
	while c >> i:
		if c >> i & 1 != cur:
			res.append(test[i - 1])
			cur = c >> i & 1
		i += 1
	res.append(test[i - 1])
	print(len(res))
	print(' '.join(res))


from math import ceil, log2, floor, sqrt
from collections import defaultdict, deque
import sys
import os.path
sys.setrecursionlimit(200000)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r+')
	sys.stdout = open('output.txt', 'w')

def MI():
	return map(int, input().split())
mod = 10 ** 9 + 7

def div(n):
	l = []
	while n > 0:
		l.append(n % 2)
		n = n // 2
	return l

def solve():
	n = int(input())
	l = div(n)
	ans = []
	if n == 0:
		print(2)
		print(1, 1)
		return
	last = 1
	for i in range(len(l)):
		if l[i] == 0:
			if last == 0:
				ans[-1] = 2 * ans[-1] + 1
				ans[-2] = 2 * ans[-2] + 1
			else:
				ans.append((1 << i + 1) - 1)
				ans.append((1 << i + 1) - 1)
			last = 0
		else:
			if len(ans):
				ans[-1] = 2 * ans[-1] + 1
			else:
				ans.append(1)
			last = 1
	print(len(ans))
	print(*ans)
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	bit = bin(n)[2:]
	if n == 2 ** len(bit) - 1:
		print(1)
		print(n)
	elif n == 2 ** len(bit):
		print(2)
		print(2 ** len(bit) - 1, 2 ** (len(bit) + 1) - 1)
	else:
		a = 1
		ans = []
		b = len(bit)
		c = 2 ** b - 1
		ans.append(c)
		for j in range(len(bit)):
			if bit[j] == '1':
				if a == 1:
					continue
				else:
					b = len(bit[j:])
					c = 2 ** b - 1
					ans.append(c)
					a = 1
			elif a == 0:
				continue
			else:
				b = len(bit[j:])
				c = 2 ** b - 1
				ans.append(c)
				a = 0
		print(len(ans))
		print(*ans)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys
import heapq

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print(2)
		print(1, 1)
		continue
	arr = []
	for i in range(62):
		if n & 1 << i > 0:
			arr.append(1)
		else:
			arr.append(0)
	arr.reverse()
	ind = 0
	for i in range(len(arr)):
		if arr[i] == 1:
			ind = i
			break
	qu = len(arr) - ind
	arr = arr[ind:]
	ans = []
	ans.append(2 ** qu - 1)
	for i in range(1, len(arr)):
		qu = len(arr) - i
		if arr[i] != arr[i - 1]:
			ans.append(2 ** qu - 1)
	print(len(ans))
	print(*ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n == 0:
		print(2)
		print(1, 1)
		continue
	ans = []
	msb = int(math.log2(n))
	cnt = 0
	for i in range(msb, -1, -1):
		if n & 1 << i:
			if cnt % 2 == 0:
				cnt += 1
				ans.append((1 << i + 1) - 1)
		elif cnt % 2 != 0:
			cnt += 1
			ans.append((1 << i + 1) - 1)
	print(len(ans))
	for x in ans:
		print(x, end=' ')
	print()


t = int(input())
for i in range(t):
	c = int(input())
	li = []
	a = bin(c).replace('0b', '')
	if c == 0:
		print(2)
		print(1, 1)
	else:
		s = len(a)
		for j in range(len(a)):
			if j == 0:
				li.append(2 ** s - 1)
			elif a[j] != a[j - 1]:
				li.append(2 ** (s - j) - 1)
		print(len(li))
		print(*li)


def do(n):
	b = bin(n)
	l = len(b)
	v = 2 ** (l - 2) - 1
	va = [v]
	bv = bin(v)
	for i in range(2, l):
		if b[i] != bv[i]:
			vi = 2 ** (l - i) - 1
			va.append(vi)
			v ^= vi
			bv = bin(v)
	return va
for _ in range(int(input())):
	l = do(int(input()))
	print(len(l))
	print(*l)


import math
for _ in range(int(input())):
	c = int(input())
	if c == 0:
		print(2)
		print(1, 1)
		continue
	ans = []
	while c:
		s = int(math.log(c, 2)) + 1
		a = (1 << s) - 1
		ans.append(a)
		c = c ^ a
	print(len(ans))
	for i in range(len(ans) - 1):
		print(ans[i], end=' ')
	print(ans[-1])


for q in range(int(input())):
	n = int(input())
	s = bin(n).replace('0b', '')
	ln = len(s)
	t = '1'
	l = []
	if n == 0:
		print(2)
		print(1, 1)
	else:
		for i in range(ln):
			if s[i] == t:
				t = '0' if t == '1' else '1'
				l.append(2 ** (ln - i) - 1)
		print(len(l))
		print(*l)


import bisect
l = [2 ** i - 1 for i in range(1, 61)]

def solve(c):
	x = l[bisect.bisect_right(l, c) - 1]
	y = l[bisect.bisect_left(l, c)]
	if x == y:
		return [x]
	if x ^ y == c:
		return [x, y]
	return solve(y - c) + [y]
for _ in range(int(input())):
	c = int(input())
	result = solve(c)
	print(len(result))
	print(*result)


from sys import stdin

def ii():
	return int(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline()
t = 1
t = ii()
for _ in range(t):
	n = ii()
	if n == 0:
		print(2)
		print(1, 1)
	else:
		l1 = []
		tmp = 0
		st = 1 << 61
		while st:
			if tmp & st != n & st:
				tmp = tmp ^ (st << 1) - 1
				l1.append((st << 1) - 1)
			st >>= 1
		print(len(l1))
		print(*l1)


import math

class sol:

	def __init__(self):
		self.n = n
		self.p = []

	def su(self, n):
		if n == 0:
			self.p.append(1)
			self.p.append(1)
		while n > 0:
			if math.ceil(math.log(n + 1) / math.log(2)) == math.floor(math.log(n + 1) / math.log(2)):
				self.p.append(n)
				n = 0
			elif math.ceil(math.log(n) / math.log(2)) == math.floor(math.log(n) / math.log(2)):
				d = math.floor(math.log(n) / math.log(2))
				a1 = pow(2, d) - 1
				b1 = pow(2, d + 1) - 1
				self.p.append(a1)
				self.p.append(b1)
				n = 0
			else:
				d = int(math.log(n) // math.log(2))
				k = pow(2, d + 1) - 1
				self.p.append(k)
				diff = k - n
				n = diff

	def col(self, n):
		if math.ceil(math.log(n + 1) / math.log(2)) == math.floor(math.log(n + 1) / math.log(2)):
			self.p.append(n)
		elif math.ceil(math.log(n) / math.log(2)) == math.floor(math.log(n) / math.log(2)):
			d = math.floor(math.log(n) / math.log(2))
			a1 = pow(2, d) - 1
			b1 = pow(2, d + 1) - 1
			self.p.append(a1)
			self.p.append(b1)
		else:
			d = int(math.log(n) // math.log(2))
			k = pow(2, d + 1) - 1
			self.p.append(k)
			diff = k - n
			self.col(diff)
for _ in range(int(input())):
	n = int(input())
	s = sol()
	s.su(n)
	print(len(s.p))
	print(*s.p)


t = int(input())
nums = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247, 4503599627370495, 9007199254740991, 18014398509481983, 36028797018963967, 72057594037927935, 144115188075855871, 288230376151711743, 576460752303423487, 1152921504606846975]
for i in range(t):
	c = int(input())
	if c == 0:
		print(2)
		print(1, end=' ')
		print(1)
	else:
		c = '{0:b}'.format(c)
		lenc = len(c)
		ans = []
		rest1 = True
		ans.append(nums[lenc - 1])
		for j in range(1, lenc):
			if c[j] == '0' and rest1 == True:
				ans.append(nums[lenc - (j + 1)])
				rest1 = False
			elif c[j] == '1' and rest1 == False:
				ans.append(nums[lenc - (j + 1)])
				rest1 = True
		print(len(ans))
		for j in sorted(ans):
			print(j, end=' ')
		print()


for _ in range(int(input())):
	a = int(input())
	b = bin(a)[2:]
	if a == 0:
		print(2)
		print(1, 1)
		continue
	ans = []
	ans.append(int('1' * len(b), 2))
	for i in range(1, len(b)):
		if b[i] != b[i - 1]:
			ans.append(int('1' * (len(b) - i), 2))
	print(len(ans))
	ans.sort()
	for i in ans:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	b1 = list(bin(n)[2:])
	v = str(0)
	ans = []
	n1 = len(b1)
	for i in range(n1):
		if b1[i] == v:
			continue
		else:
			ans.append(2 ** (n1 - i) - 1)
			if v == str(0):
				v = str(1)
			else:
				v = str(0)
	if n == 0:
		print(2)
		print(*[1, 1])
	else:
		print(len(ans))
		print(*ans)


t = int(input())
for i in range(t):
	C = int(input())
	if C == 0:
		print(2)
		print('1 1')
		continue
	if C == 1:
		print(1)
		print(1)
		continue
	c = bin(C)[2:]
	if '0' in c:
		n = len(c)
		ans = [2 ** n - 1]
		for i in range(n - 1):
			if c[i + 1] != c[i]:
				ans.append(2 ** (n - i - 1) - 1)
		print(len(ans))
		print(' '.join([str(x) for x in ans]))
	else:
		print(1)
		print(C)


for _ in range(int(input())):
	n = int(input())
	k = 1
	if n == 0:
		print(2)
		print(1, 1)
		continue
	while k <= n:
		k = k << 1
	if k >> 1 == n and n != 1:
		print(2)
		print(n - 1, k - 1)
		continue
	k -= 1
	if k == n:
		print(1)
		print(n)
	else:
		result = [k]
		c = 1
		binary = bin(n)[2:]
		flag = 0
		k = len(binary)
		for i in range(1, k):
			if binary[i] == '0' and flag == 0:
				result.append(pow(2, k - i) - 1)
				c += 1
				flag = 1
			elif binary[i] == '1' and flag == 1:
				result.append(pow(2, k - i) - 1)
				flag = 0
				c += 1
		print(c)
		result.reverse()
		print(*result)


t = int(input())
for tt in range(t):
	num = int(input())
	if num == 0:
		print(2)
		print('1 1')
	elif num == 1:
		print(1)
		print(1)
	else:
		c = bin(num)[2:]
		if '0' in c:
			n = len(c)
			ans = [2 ** n - 1]
			for i in range(n - 1):
				if c[i + 1] != c[i]:
					ans.append(2 ** (n - i - 1) - 1)
			print(len(ans))
			print(' '.join([str(x) for x in ans]))
		else:
			print(1)
			print(num)


def bintodec(n):
	stack = []
	while n != 0:
		stack.append(str(n % 2))
		n = n // 2
	s = ''
	while stack != []:
		s += stack.pop()
	return s
t = int(input())
for t in range(t):
	c = int(input())
	c = bintodec(c)
	parity = 0
	ans = []
	if c == '':
		print(2)
		print('1 1')
		continue
	for i in range(0, len(c)):
		if c[i] == '1':
			if parity == 0:
				ans.append(len(c) - i)
				parity = 1
		elif c[i] == '0':
			if parity == 1:
				ans.append(len(c) - i)
				parity = 0
	ans = [str(2 ** x - 1) for x in ans]
	print(len(ans))
	print(' '.join(ans))


for _ in range(int(input())):
	c = int(input())
	b = bin(c)[2:]
	l = []
	for i in b:
		l.append(int(i))
	ans = []
	f = 0
	n1 = len(l)
	if c == 0:
		print(2)
		print(1, 1)
		continue
	for i in range(len(l)):
		if l[i] == 1:
			if f == 0:
				f = 1
				ans.append(pow(2, n1 - i) - 1)
		elif f == 1:
			ans.append(pow(2, n1 - i) - 1)
			f = 0
	print(len(ans))
	print(*ans)