Johnny is playing with a large binary number, $\mbox{B}$. The number is so large that it needs to be compressed into an array of integers, $\mbox{A}$, where the values in even indices ($0,2,4,\ldots$) represent some number of consecutive $1$ bits and the values in odd indices ($1,3,5,\ldots$) represent some number of consecutive $0$ bits in alternating substrings of $\mbox{B}$.       

For example, suppose we have array $A=\{4,1,3,2,4\}$. $\boldsymbol{A_0}$ represents $\text{"}1111\text{"}$, $\boldsymbol{A_1}$ represents $\text{"}0\text{"}$, $\boldsymbol{A_{2}}$ represents $\text{"}111"$, $A_3$ represents $\text{"00"}$, and $\boldsymbol{A}_4$ represents $\text{"}1111\text{"}$. The number of consecutive binary characters in the $i^{\mbox{th}}$ substring of $\mbox{B}$ corresponds to integer $A_i$, as shown in this diagram:

When we assemble the sequential alternating sequences of $1$'s and $0$'s, we get $B="11110111001111"$.

We define setCount($\mbox{B}$) to be the number of $1$'s in a binary number, $\mbox{B}$. Johnny wants to find a binary number, $\mbox{D}$, that is the smallest binary number $>B$ where setCount($\mbox{B}$) = setCount($\mbox{D}$). He then wants to compress $\mbox{D}$ into an array of integers, $\mbox{C}$ (in the same way that integer array $\mbox{A}$ contains the compressed form of binary string $\mbox{B}$).

Johnny isn't sure how to solve the problem. Given array $\mbox{A}$, find integer array $\mbox{C}$ and print its length on a new line. Then print the elements of array $\mbox{C}$ as a single line of space-separated integers.

Input Format

The first line contains a single positive integer, $\mathbf{T}$, denoting the number of test cases. Each of the $2T$ subsequent lines describes a test case over $2$ lines:

The first line contains a single positive integer, $n$, denoting the length of array $\mbox{A}$. 
The second line contains $n$ positive space-separated integers describing the respective elements in integer array $\mbox{A}$ (i.e., $A_0,A_1,\ldots,A_{n-1}$).

Constraints

$1\leq T\leq100$
$1\leq n\leq10$

Subtasks

For a $50\%$ score, $1\leq A_i\leq10^4$.
For a $\textbf{100\%}$ score, $1\leq A_i\leq10^{18}$.

Output Format

For each test case, print the following $2$ lines:  

Print the length of integer array $\mbox{C}$ (the array representing the compressed form of binary integer $\mbox{D}$) on a new line. 
Print each element of $\mbox{C}$ as a single line of space-separated integers.

It is guaranteed that a solution exists.

Sample Input 0
1
5
4 1 3 2 4

Sample Output 0
7
4 1 3 1 1 1 3

Explanation 0

$A=\{4,1,3,2,4\}$, which expands to $B=11110111001111$. We then find setCount($\mbox{B}$) $=11$. The smallest binary number $>B$ which also has eleven $\mbox{1}$'s is $D=11110111010111$. This can be reduced to the integer array $C=\{4,1,3,1,1,1,3\}$. This is demonstrated by the following figure:

Having found $\mbox{C}$, we print its length ($7$) as our first line of output, followed by the space-separated elements in $\mbox{C}$ as our second line of output.

Difficulty: MEDIUM
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:

Solutions:
T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	if N == 1:
		A = [1, 1, A[0] - 1]
	elif N == 2:
		A = [1, A[1] + 1, A[0] - 1]
	elif N & 1:
		A.append(1)
		A.append(A[-2] - 1)
		A[-4] -= 1
		A[-3] = 1
	else:
		A.append(A[-2] - 1)
		A[-4] -= 1
		A[-3] = 1
		A[-2] += 1
	while A[-1] == 0:
		A.pop()
	for i in range(len(A) - 2, 0, -1):
		if A[i] == 0:
			A[i - 1] += A[i + 1]
			del A[i:i + 2]
	print(len(A))
	print(' '.join(map(str, A)))


t = []
for q in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	if n % 2 == 0:
		nl = []
		if n > 3:
			nl = l[0:n - 3]
			if l[n - 3] - 1 == 0:
				nl[len(nl) - 1] += 1
			else:
				if l[n - 3] - 1 != 0:
					nl.append(l[n - 3] - 1)
				nl.append(1)
			nl.append(l[n - 1] + 1)
			if l[n - 2] - 1 != 0:
				nl.append(l[n - 2] - 1)
		else:
			nl.append(1)
			nl.append(l[n - 1] + 1)
			if l[n - 2] - 1 != 0:
				nl.append(l[n - 2] - 1)
		t.append(len(nl))
		t.append(nl)
		print(len(nl))
		for i in range(len(nl)):
			print(nl[i], end=' ')
		print()
	else:
		if n > 1:
			nl = l[:n - 2]
			if l[n - 2] - 1 != 0:
				nl.append(l[n - 2] - 1)
				nl.append(1)
			else:
				nl[len(nl) - 1] += 1
			nl.append(1)
			if l[n - 1] - 1 != 0:
				nl.append(l[n - 1] - 1)
		else:
			nl = []
			nl.append(1)
			nl.append(1)
			if l[0] - 1 != 0:
				nl.append(l[0] - 1)
		t.append(len(nl))
		t.append(nl)
		print(len(nl))
		for i in nl:
			print(i, end=' ')
		print()


class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))


import sys

def tidy_up(arr):
	n = len(arr)
	result = [arr[0]]
	pos = 1
	while pos < n:
		if arr[pos]:
			result.append(arr[pos])
		elif pos + 1 < n:
			result[-1] += arr[pos + 1]
			pos += 1
		pos += 1
	return result
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split(' ')]
	if n == 1:
		arr = tidy_up([1, 1, arr[-1] - 1])
	elif n == 2:
		arr = tidy_up([1, arr[-1] + 1, arr[-2] - 1])
	elif n % 2:
		arr = tidy_up(arr[:-2] + [arr[-2] - 1, 1, 1, arr[-1] - 1])
	else:
		arr = tidy_up(arr[:-3] + [arr[-3] - 1, 1, arr[-1] + 1, arr[-2] - 1])
	print(len(arr))
	print(' '.join((str(i) for i in arr)))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	if n == 1:
		a = [1, 1, a[-1] - 1]
	elif n == 2:
		a = [1, a[-1] + 1, a[-2] - 1]
	elif len(a) % 2 == 1:
		a = a[:-2] + [a[-2] - 1, 1, 1, a[-1] - 1]
		if a[-4] == 0 and len(a) >= 5:
			a = a[:-5] + [a[-5] + a[-3]] + a[-2:]
		elif a[-4] == 0:
			a = [a[-3]] + a[-2:]
	else:
		a = a[:-3] + [a[-3] - 1, 1, 1 + a[-1], a[-2] - 1]
		if a[-4] == 0:
			a = a[:-5] + [a[-5] + a[-3]] + a[-2:]
	if a[-1] == 0:
		a = a[:-1]
	print(len(a))
	print(' '.join((str(x) for x in a)))


import re
T = int(input().strip())
for t in range(0, T):
	N = int(input().strip())
	A = list(map(int, input().strip().split(' ')))
	if N == 1:
		C = [1, 1, A[0] - 1]
	elif N == 2:
		C = [1, A[1] + 1, A[0] - 1]
	elif N == 3:
		C = [A[0]] + [A[1] - 1] + [1, 1, A[2] - 1]
	elif N == 4:
		C = A[0:1] + [A[1] - 1, 1, A[3] + 1, A[2] - 1]
	elif N == 5:
		C = A[0:3] + [A[3] - 1] + [1, 1, A[4] - 1]
	elif N == 6:
		C = A[0:3] + [A[3] - 1, 1, A[5] + 1, A[4] - 1]
	elif N == 7:
		C = A[0:5] + [A[5] - 1] + [1, 1, A[6] - 1]
	elif N == 8:
		C = A[0:5] + [A[5] - 1, 1, A[7] + 1, A[6] - 1]
	elif N == 9:
		C = A[0:7] + [A[7] - 1] + [1, 1, A[8] - 1]
	else:
		C = A[0:7] + [A[7] - 1, 1, A[9] + 1, A[8] - 1]
	if C[-1] == 0:
		C = C[0:-1]
	if N == 3 or N == 4:
		if C[1] == 0:
			C[0] += 1
			C = [C[0]] + C[3:]
	elif N == 5 or N == 6:
		if C[3] == 0:
			C[2] += 1
			C = C[0:3] + C[5:]
	elif N == 7 or N == 8:
		if C[5] == 0:
			C[4] += 1
			C = C[0:5] + C[7:]
	elif N == 9 or N == 10:
		if C[7] == 0:
			C[6] += 1
			C = C[0:7] + C[9:]
	print(len(C))
	t = str(C)[1:-1]
	t = re.sub(',', '', t)
	print(t)


T = int(input())
for i in range(T):
	n = int(input())
	vals = list((int(x) for x in input().split(' ')))
	if n == 1:
		if vals[0] == 1:
			vals = [1, 1]
		else:
			vals = [1, 1, vals[0] - 1]
	elif n == 2:
		if vals[0] == 1:
			vals[1] += 1
		else:
			vals = [1, vals[1] + 1, vals[0] - 1]
	elif n & 1:
		if vals[-2] > 1:
			vals[-2] -= 1
			vals.insert(-1, 1)
			vals.insert(-1, 1)
		else:
			vals[-3] += 1
		vals[-1] -= 1
		if vals[-1] == 0:
			vals.pop()
	elif vals[-3] > 1:
		vals[-3] -= 1
		toAdd = vals[-2] - 1
		vals[-2] = 1
		vals[-1] += 1
		if toAdd > 0:
			vals.append(toAdd)
	else:
		vals[-4] += 1
		vals[-3] = vals[-1] + 1
		if vals[-2] > 1:
			vals[-2] -= 1
		else:
			vals.pop()
		vals.pop()
	print(len(vals))
	print(' '.join([str(x) for x in vals]))


num_cases = int(input())
for i in range(num_cases):
	num_elems = input()
	elems = list(map(int, input().split()))
	if len(elems) == 1:
		if elems[0] == 1:
			print('2')
			print('1 1')
		else:
			print('3')
			print('1 1 ' + str(elems[0] - 1))
		continue
	if len(elems) == 2:
		if elems[0] == 1:
			print('2')
			print('1 ' + str(elems[1] + 1))
		else:
			print('3')
			print('1 ' + str(elems[1] + 1) + ' ' + str(elems[0] - 1))
		continue
	if len(elems) % 2 == 1:
		if elems[-1] - 1 == 0:
			if elems[-2] - 1 == 0:
				del elems[-2]
				elems[-2] += 1
			else:
				elems.insert(-1, 1)
				elems[-3] -= 1
		else:
			elems[-1] -= 1
			elems.insert(-1, 1)
			if elems[-3] - 1 == 0:
				del elems[-3]
				elems[-3] += 1
			else:
				elems[-3] -= 1
				elems.insert(-2, 1)
		print(str(len(elems)))
		print(' '.join(map(str, elems)))
		continue
	else:
		if elems[-2] - 1 == 0:
			del elems[-2]
			elems[-1] += 1
			if elems[-2] - 1 == 0:
				del elems[-2]
				elems[-2] += 1
			else:
				elems.insert(-1, 1)
				elems[-3] -= 1
		else:
			elems[-1] += 1
			elems.append(elems[-2] - 1)
			del elems[-3]
			if elems[-3] - 1 == 0:
				elems[-4] += 1
				del elems[-3]
			else:
				elems[-3] -= 1
				elems.insert(-2, 1)
		print(str(len(elems)))
		print(' '.join(map(str, elems)))
		continue
	binary = []
	bit = '1'
	for i in range(len(elems)):
		binary.extend(bit * int(elems[i]))
		if bit == '1':
			bit = '0'
		else:
			bit = '1'
	binary = binary[::-1]
	if binary[0] == '0':
		binary.insert(0, '0')
	else:
		found = False
		for i in range(1, len(binary)):
			if binary[i] == '0':
				binary[i] = '1'
				binary[i - 1] = '0'
				found = True
				break
		if not found:
			binary.insert(0, '0')
	binary = binary[::-1]
	arr = [0]
	cur_char = binary[0]
	i = 0
	while i < len(binary):
		if binary[i] == cur_char:
			arr[len(arr) - 1] += 1
		else:
			arr.append(1)
			cur_char = binary[i]
		i += 1
	final_arr = [str(x) for x in arr]
	print(str(len(final_arr)))
	print(' '.join(final_arr))


from math import log
from math import pow
tcount = int(input().strip())
for tc in range(0, tcount):
	num = int(input().strip())
	arr = list(map(int, input().strip().split(' ')))
	if num % 2 == 1:
		if num >= 3:
			if arr[-1] != 1 and arr[-2] != 1:
				newlastnum = arr[-1] - 1
				next2last = arr[-2] - 1
				print(num + 2)
				print(' '.join(list(map(str, arr[:-2])) + [str(next2last), '1', '1', str(newlastnum)]))
			elif arr[-1] == 1 and arr[-2] != 1:
				next2last = arr[-2] - 1
				print(num + 1)
				print(' '.join(list(map(str, arr[:-2])) + [str(next2last), '1', '1']))
			elif arr[-1] != 1 and arr[-2] == 1:
				newlastnum = arr[-1] - 1
				next3last = arr[-3] + 1
				print(num)
				print(' '.join(list(map(str, arr[:-3])) + [str(next3last), '1', str(newlastnum)]))
			else:
				next3last = arr[-3] + 1
				print(num - 1)
				print(' '.join(list(map(str, arr[:-3])) + [str(next3last), '1']))
		elif arr[0] != 1:
			print(num + 2)
			print(' '.join(['1', '1', str(arr[0] - 1)]))
		else:
			print(num + 1)
			print(' '.join(['1', '1']))
	elif num > 3:
		if arr[-3] != 1 and arr[-2] != 1:
			next3last = arr[-3] - 1
			next2last = 1 + arr[-1]
			newlastnum = arr[-2] - 1
			print(num + 1)
			print(' '.join(list(map(str, arr[:-3])) + [str(next3last), '1', str(next2last), str(newlastnum)]))
		elif arr[-3] == 1 and arr[-2] != 1:
			print(num - 1)
			next4last = arr[-4] + 1
			next2last = arr[-1] + 1
			newlastnum = arr[-2] - 1
			print(' '.join(list(map(str, arr[:-4])) + [str(next4last), str(next2last), str(newlastnum)]))
		elif arr[-3] != 1 and arr[-2] == 1:
			print(num)
			next3last = arr[-3] - 1
			next2last = 1
			newlastnum = arr[-1] + 1
			print(' '.join(list(map(str, arr[:-3])) + [str(next3last), str(next2last), str(newlastnum)]))
		else:
			print(num - 2)
			next3last = arr[-4] + 1
			newlastnum = arr[-1] + 1
			print(' '.join(list(map(str, arr[:-4])) + [str(next3last), str(newlastnum)]))
	elif arr[0] > 1:
		print(num + 1)
		print(' '.join(['1', str(arr[1] + 1), str(arr[0] - 1)]))
	else:
		print(num)
		print(' '.join(['1', str(arr[0] + arr[1])]))


def get_near(A):
	if len(A) == 2:
		return [n for n in [1, A[1] + 1, A[0] - 1] if n]
	if len(A) == 1:
		return [n for n in [1, 1, A[0] - 1] if n]
	if len(A) % 2 == 0:
		zero = -3
	else:
		zero = -2
	count_list = [[int(not n % 2), A[n]] for n in range(len(A))]
	count_list[zero][1] = count_list[zero][1] - 1
	count_list[zero + 1][1] = count_list[zero + 1][1] - 1
	count_list = count_list[:zero + 1] + [[1, 1], [0, 1]] + count_list[zero + 1:][::-1]
	res = [count_list[0]]
	for e in count_list[1:]:
		if e[1] != 0:
			if e[0] == res[-1][0]:
				res[-1][1] = res[-1][1] + e[1]
			else:
				res.append(e)
	return list(map(lambda x: x[1], res))
N = int(input().strip())
for i in range(N):
	l = int(input().strip())
	input_l = input().strip().split()
	A = list(map(int, input_l))
	C = get_near(A)
	print(len(C))
	print(' '.join(map(str, C)))


def solve(n, A):
	if n == 0:
		A.append(1)
	elif n == 1:
		if A[0] == 1:
			A.append(1)
		else:
			A[:] = [1, 1, A[0] - 1]
	elif n == 2:
		if A[0] == 1:
			A[1] += 1
		else:
			A[:] = [1, A[1] + 1, A[0] - 1]
	else:
		x = (n - 1) // 2 * 2
		A[x - 1:] = [A[x - 1] - 1, 1, 1 if x == n - 1 else 1 + A[x + 1], A[x] - 1]
		if A[-4] == 0:
			A[-5:-2] = [A[-5] + 1]
		if A[-1] == 0:
			A.pop()
	return A
T = int(input())
for test in range(T):
	n = int(input())
	A = [int(x) for x in input().split()]
	C = solve(n, A)
	print(len(C))
	print(*C)


t = int(input())
for _ in range(t):
	n = int(input())
	L = [int(x) for x in input().strip().split()]
	if len(L) == 1:
		if L[-1] == 1:
			C = [1, 1]
		else:
			C = [1, 1, L[-1] - 1]
	elif len(L) % 2:
		if L[-2] == 1:
			if L[-1] == 1:
				C = L[:-3] + [L[-3] + 1, 1]
			else:
				C = L[:-3] + [L[-3] + 1, 1, L[-1] - 1]
		elif L[-1] == 1:
			C = L[:-2] + [L[-2] - 1, 1, 1]
		else:
			C = L[:-2] + [L[-2] - 1, 1, 1, L[-1] - 1]
	elif len(L) == 2:
		if L[-2] == 1:
			C = [1, L[-1] + 1]
		else:
			C = [1, L[-1] + 1, L[-2] - 1]
	elif L[-3] == 1:
		if L[-2] == 1:
			C = L[:-4] + [L[-4] + 1, L[-1] + 1]
		else:
			C = L[:-4] + [L[-4] + 1, L[-1] + 1, L[-2] - 1]
	elif L[-2] == 1:
		C = L[:-3] + [L[-3] - 1, 1, L[-1] + 1]
	else:
		C = L[:-3] + [L[-3] - 1, 1, L[-1] + 1, L[-2] - 1]
	print(len(C))
	print(*C)


def next(l):
	if len(l) % 2:
		if len(l) == 1:
			return [1, 1] + ([l[0] - 1] if l[0] > 1 else [])
		if l[-2] == 1:
			return l[:-3] + [l[-3] + 1, 1] + ([l[-1] - 1] if l[-1] > 1 else [])
		return l[:-2] + [l[-2] - 1, 1, 1] + ([l[-1] - 1] if l[-1] > 1 else [])
	else:
		if len(l) == 0:
			return None
		if len(l) == 2:
			return [1, l[-1] + 1] + ([l[-2] - 1] if l[-2] > 1 else [])
		if l[-3] == 1:
			return l[:-4] + [l[-4] + 1, l[-1] + 1] + ([l[-2] - 1] if l[-2] > 1 else [])
		return l[:-3] + [l[-3] - 1, 1, l[-1] + 1] + ([l[-2] - 1] if l[-2] > 1 else [])
test_number = int(input())
for _ in range(test_number):
	input()
	l = list(map(int, input().split()))
	res = next(l)
	print(len(res))
	print(*res, sep=' ')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if len(a) == 1:
		a = [1] + [1] + [a[0] - 1]
	elif len(a) == 2:
		a = [1] + [a[1] + 1] + [a[0] - 1]
	elif len(a) == 3:
		a = [a[0]] + [a[1] - 1] + [1] + [1] + [a[2] - 1]
	elif len(a) == 4:
		a = [a[0]] + [a[1] - 1] + [1] + [a[3] + 1] + [a[2] - 1]
	elif len(a) % 2 == 1:
		a[-2] -= 1
		a = a[:-1] + [1] + [1] + [a[-1] - 1]
	else:
		a[-3] -= 1
		a = a[:-2] + [1] + [a[-1] + 1] + [a[-2] - 1]
	for j in range(len(a) - 1, max(-1, len(a) - 5), -1):
		if a[j] == 0:
			if j == len(a) - 1:
				a = a[:-1]
			else:
				a = a[:j - 1] + [a[j - 1] + 1] + a[j + 2:]
	print(len(a))
	print(' '.join(map(str, a)))


num1 = input()
list = []

def output(list):
	len1 = len(list)
	if len1 is 1:
		list.insert(-1, 1)
		if int(list[1]) != int(1):
			list.insert(-1, 1)
			list[2] = str(int(list[2]) - 1)
	elif len1 is 2:
		list.insert(2, str(int(list[0]) - 1))
		list[0] = str(1)
		list[1] = str(int(list[1]) + 1)
	else:
		num = 0
		if len1 % 2 is 1:
			num = int(len1 / 2) * 2
		else:
			num = len1 - 2
		if len1 % 2 is 1:
			list[num - 1] = str(int(list[num - 1]) - 1)
			list.insert(num, '1')
			list.insert(num, '1')
			list[num + 2] = str(int(list[num + 2]) - 1)
		else:
			list[num - 1] = str(int(list[num - 1]) - 1)
			num2 = list[num]
			list[num] = str(int(list[num + 1]) + 1)
			list[num + 1] = str(int(num2) - 1)
			list.insert(num, '1')
	cnt = 0
	if True:
		flag = 0
		for i in list:
			flag = 0
			if int(i) is 0:
				sum = 0
				if cnt + 1 < len(list):
					sum = int(list[cnt + 1])
					flag = 1
				list[cnt - 1] = str(int(list[cnt - 1]) + sum)
				list.pop(cnt)
				if int(flag) == 1:
					list.pop(cnt)
					cnt = cnt + 1
			else:
				cnt = cnt + 1
	print(len(list))
	for i in list:
		print(i, end='')
		print(' ', end='')
	print()
for k in range(int(num1)):
	cnt = input()
	list = []
	list = input().split()
	output(list)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	if n & 1:
		b.append(1)
		if n > 1:
			b[n - 2] -= 1
		b.append(b[n - 1] - 1)
		b[n - 1] = 1
	else:
		b.append(b[n - 2] - 1)
		b[n - 2] = 1
		b[n - 1] += 1
		if n > 2:
			b[n - 3] -= 1
	x = False
	a = []
	for i in b:
		if x:
			if a:
				a[-1] += i
			x = False
		elif i:
			a.append(i)
		else:
			x = True
	print(len(a))
	print(*a)


def pp(A, *b):
	for a in A:
		print(a, end=' ')
	for x in b:
		print(x, end=' ')
	print()
T = int(input())
for t in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	if len(A) % 2:
		if len(A) == 1:
			if A[0] == 1:
				print(2)
				print(1, 1)
			else:
				print(3)
				print(1, 1, A[0] - 1)
		elif A[-2] == 1:
			A[-3] += 1
			if A[-1] == 1:
				print(len(A) - 1)
				pp(A[:-2], 1)
			else:
				A[-1] -= 1
				print(len(A))
				pp(A)
		else:
			A[-2] -= 1
			if A[-1] == 1:
				print(len(A) + 1)
				pp(A[:-1], 1, 1)
			else:
				print(len(A) + 2)
				pp(A[:-1], 1, 1, A[-1] - 1)
	elif len(A) == 2:
		if A[0] == 1:
			print(2)
			print(1, A[1] + 1)
		else:
			print(3)
			print(1, A[1] + 1, A[0] - 1)
	elif A[-3] == 1:
		A[-4] += 1
		if A[-2] == 1:
			A[-1] += 1
			print(len(A) - 2)
			pp(A[:-3], A[-1])
		else:
			A[-1] += 1
			print(len(A) - 1)
			pp(A[:-3], A[-1], A[-2] - 1)
	else:
		A[-3] -= 1
		if A[-2] == 1:
			print(len(A))
			pp(A[:-2], 1, A[-1] + 1)
		else:
			print(len(A) + 1)
			pp(A[:-2], 1, A[-1] + 1, A[-2] - 1)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		ones = a[0] - 1
		if ones >= 1:
			a[0] -= 1
			a.insert(0, 1)
			a.insert(0, 1)
		else:
			a.append(1)
	elif n == 2:
		ones = a[0]
		if ones > 1:
			a.insert(0, 1)
			temp = a[1] - 1
			a[1] = a[2] + 1
			a[2] = temp
		else:
			a[1] += 1
	elif n % 2 == 0:
		ones = a[n - 2]
		zeros = a[n - 3]
		if ones > 1 and zeros > 1:
			a[n - 3] -= 1
			a[n - 2] -= 1
			a.insert(n - 2, 1)
			temp = a[n - 1]
			a[n - 1] = a[n] + 1
			a[n] = temp
		elif zeros > 1 and ones == 1:
			a[n - 1] += 1
			a[n - 3] -= 1
		elif zeros == 1 and ones > 1:
			a[n - 2] -= 1
			a[n - 4] += 1
			a[n - 3] += a[n - 1]
			a = a[0:n - 1]
		else:
			a[n - 1] += 1
			a[n - 4] += 1
			a = a[0:n - 3] + a[n - 1:]
	else:
		ones = a[n - 1]
		zeros = a[n - 2]
		if ones > 1 and zeros > 1:
			a[n - 1] -= 1
			a[n - 2] -= 1
			a.insert(n - 1, 1)
			a.insert(n - 1, 1)
		elif zeros > 1 and ones == 1:
			a[n - 2] -= 1
			a.insert(n - 1, 1)
		elif zeros == 1 and ones > 1:
			a[n - 1] -= 1
			a[n - 3] += 1
		else:
			a[n - 3] += 1
			a = a[0:n - 1]
	print(len(a))
	print(*a)
	t -= 1


class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))


class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))


class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))


T = int(input())
for i in range(T):
	n = int(input())
	A = list(map(lambda x: int(x), input().split()))
	if n % 2 == 1 and n > 2:
		if A[-1] == 1 and A[-2] == 1:
			A = A[:-3] + [A[-3] + 1] + [1]
		elif A[-1] > 1 and A[-2] == 1:
			A = A[:-3] + [A[-3] + 1] + [1] + [A[-1] - 1]
		elif A[-2] > 1:
			A = A[:-2] + [A[-2] - 1] + [1] + [1] + ([A[-1] - 1] if A[-1] - 1 > 0 else [])
	elif n == 1:
		A = [1, 1] + ([A[-1] - 1] if A[-1] - 1 > 0 else [])
	elif n == 2:
		A = [1] + [A[-1] + 1] + ([A[-2] - 1] if A[-2] - 1 > 0 else [])
	elif n % 2 == 0:
		if A[-2] == 1:
			A = (A[:-3] + [A[-3] - 1] + [1] if A[-3] - 1 > 0 else A[:-4] + [A[-4] + 1]) + [A[-1] + 1]
		else:
			A = (A[:-3] + [A[-3] - 1] + [1] if A[-3] - 1 > 0 else A[:-4] + [A[-4] + 1]) + [A[-1] + 1] + [A[-2] - 1]
	print(len(A))
	print(*A)


for _ in range(int(input())):
	len_A = int(input())
	A = [int(ai) for ai in input().split()]
	code = [A.pop(), A.pop() - 1, 1] if len_A & 1 == 0 else [0, A.pop() - 1, 1]
	code += [1, 0, 0] if len_A <= 2 else [1, A.pop() - 1, A.pop()]
	code.reverse()
	if code[1] == 0:
		code[0] += code[2]
		code[2] = 0
	if code[4] == 0:
		code[5] += code[3]
		code[3] = 0
	if code[5] > 0:
		code[3] += code[5]
		code[5] = 0
	A += (val for val in code if val > 0)
	print(len(A))
	for ai in A:
		print(ai, end=' ')
	print()


import sys
from itertools import groupby
_debug = False
_debug = True

def dprint(*args):
	global _debug
	if _debug:
		print(' '.join([str(x) for x in args]))

def findSmallest(A):
	i = -1
	B = A.copy()
	if len(A) % 2:
		i = sum(A[:-1])
		if len(B) == 1:
			B.insert(0, 1)
			B.insert(1, 1)
			B[-1] -= 1
		else:
			B[-1] -= 1
			B[-2] -= 1
			if B[-2] == 0:
				B[-3] += 1
				del B[-2]
				B.insert(-1, 1)
			else:
				B.insert(-1, 1)
				B.insert(-1, 1)
	else:
		i = sum(A[:-2])
		if len(A) == 2:
			B.insert(0, 1)
			B[-2] = A[-1] + 1
			B[-1] = A[-2] - 1
		else:
			B[-3] -= 1
			if B[-3] == 0:
				B[-4] += 1
				del B[-3]
				B[-2] = A[-1] + 1
				B[-1] = A[-2] - 1
			else:
				B.insert(-2, 1)
				B[-2] = A[-1] + 1
				B[-1] = A[-2] - 1
	B = list(filter(lambda x: x != 0, B))
	return B
T = int(input())
for t in range(T):
	n = int(input())
	A = list(map(int, input().strip().split()))
	B = findSmallest(A)
	print(len(B))
	print(' '.join(list(map(str, B))))


class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		if a[0] == 1:
			a.append(1)
		else:
			a[0] -= 1
			a = [1, 1] + a
		print(len(a))
		print(' '.join(map(str, a)))
		continue
	if n == 2:
		if a[0] == 1:
			a[1] += 1
		else:
			a.append(a[0] - 1)
			a[0] = 1
			a[1] += 1
		print(len(a))
		print(' '.join(map(str, a)))
		continue
	if n % 2 == 0:
		if a[-2] == 1 and a[-3] == 1:
			a[-4] += a[-2]
			a[-3] += a[-1]
			a.pop()
			a.pop()
		elif a[-2] == 1:
			a[-1] += 1
			a[-3] -= 1
		elif a[-3] == 1:
			zeros = a.pop() + 1
			ones = a.pop() - 1
			a.pop()
			a[-1] += 1
			a.append(zeros)
			a.append(ones)
		else:
			zeros = a.pop() + 1
			ones = a.pop() - 1
			a[-1] -= 1
			a.append(1)
			a.append(zeros)
			a.append(ones)
	else:
		ones = a.pop()
		ones -= 1
		if a[-1] == 1:
			a[-2] += 1
		else:
			a[-1] -= 1
			a.append(1)
			a.append(1)
		if ones > 0:
			a.append(ones)
	print(len(a))
	print(' '.join(map(str, a)))


for _ in range(int(input().strip())):
	n = int(input())
	A = [int(x) for x in input().strip().split()]
	if len(A) % 2 == 1:
		if len(A) > 1:
			A[-2] -= 1
		A.append(1)
		A.append(A[-2] - 1)
		A[-3] = 1
	else:
		if len(A) > 2:
			A[-3] -= 1
		A[-1] += 1
		A.append(A[-2] - 1)
		A[-3] = 1
	for i in range(len(A)):
		if i < len(A) - 1 and A[i] == 0:
			A[i - 1:i + 2] = [A[i - 1] + A[i + 1]]
		if i == len(A) - 1 and A[i] == 0:
			A.pop(-1)
	print(len(A))
	print(*A)


class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))


T = int(input(''))
for t in range(T):
	n = int(input(''))
	A = input('')
	A = [int(a) for a in A.split(' ')]
	C = A[:]
	if len(C) == 1:
		C[0] -= 1
		C.insert(0, 1)
		C.insert(0, 1)
		if C[2] == 0:
			C = C[:2]
		print(len(C))
		print(' '.join([str(c) for c in C]))
		continue
	elif len(C) == 2:
		if C[0] > 1:
			C.append(C[0] - 1)
		C[0] = 1
		C[1] += 1
		print(len(C))
		print(' '.join([str(c) for c in C]))
		continue
	even = n % 2 == 0
	even_num = 0
	if even:
		even_num = C.pop()
	z = C.pop()
	y = C.pop()
	if y > 1:
		C.append(y - 1)
		C.append(1)
		if even:
			C.append(even_num + 1)
		else:
			C.append(1)
		C.append(z - 1)
	else:
		x = C.pop()
		C.append(x + 1)
		if even:
			C.append(even_num + 1)
		else:
			C.append(1)
		C.append(z - 1)
	if C[-1] == 0:
		C = C[:-1]
	print(len(C))
	print(' '.join([str(c) for c in C]))


def next_list(n1, n0):
	if n1 > 1:
		return [1, n0, n1 - 1]
	return [1, n0]

def merge(l1, l2):
	if len(l1) % 2:
		l1[-1] += l2[0]
		l1.extend(l2[1:])
	else:
		l1.extend(l2)

def main(l):
	n = len(l)
	if n == 1:
		return [1, 1, l[0] - 1] if l[0] > 1 else [1, 1]
	elif n == 2:
		return [1, l[1] + 1, l[0] - 1] if l[0] > 1 else [1, l[1] + 1]
	elif n % 2:
		a = l.pop()
		l[-1] -= 1
		if not l[-1]:
			l.pop()
		merge(l, next_list(a, 1))
		return l
	else:
		(a, b) = l[-2:]
		del l[-2:]
		l[-1] -= 1
		if not l[-1]:
			del l[-1]
		merge(l, next_list(a, b + 1))
		return l
for _ in range(int(input())):
	n = int(input())
	(*l,) = map(int, input().split())
	l = main(l)
	print(len(l))
	print(*l)


cases = int(input().strip())
while cases:
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	offset = 0
	if n == 1:
		m = 3
		c = [1, 1, a[0] - 1]
	elif n == 2:
		m = 3
		c = [1, a[1] + 1, a[0] - 1]
	else:
		while n - offset > 4:
			offset += 2
		if n - offset == 3:
			a.append(0)
		c = []
		c.extend(a[:offset])
		a_rt = a[offset:]
		if a_rt[1] > 1 and a_rt[2] > 1:
			c.extend([a_rt[0], a_rt[1] - 1, 1, a_rt[3] + 1, a_rt[2] - 1])
		elif a_rt[1] > 1 and a_rt[2] == 1:
			c.extend([a_rt[0], a_rt[1] - 1, 1, a_rt[3] + 1])
		elif a_rt[1] == 1 and a_rt[2] > 1:
			c.extend([a_rt[0] + 1, a_rt[3] + 1, a_rt[2] - 1])
		else:
			c.extend([a_rt[0] + 1, a_rt[3] + 1])
	while c[-1] == 0:
		c.pop()
	m = len(c)
	print(m)
	out_line = ' '.join(map(str, c))
	while not out_line[-1].isdigit():
		out_line.strip()
	print(out_line)
	cases -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		c = [1, 1]
		if a[0] > 1:
			c.append(a[0] - 1)
	elif n == 2:
		if a[0] > 1:
			c = [1, a[1] + 1, a[0] - 1]
		else:
			c = [1, 1 + a[1]]
	elif n % 2 == 1:
		c = a[:n - 2]
		if a[n - 2] == 1:
			c[-1] += 1
		else:
			c += [a[n - 2] - 1, 1]
		c.append(1)
		if a[n - 1] > 1:
			c.append(a[n - 1] - 1)
	else:
		c = a[:n - 3]
		if a[n - 3] > 1:
			c += [a[n - 3] - 1, 1]
		else:
			c[-1] += 1
		c.append(a[n - 1] + 1)
		if a[n - 2] > 1:
			c.append(a[n - 2] - 1)
	print(len(c))
	print(*c)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(temp) for temp in input().split()]
	if n % 2 != 0:
		if n == 1:
			if l[0] - 1 != 0:
				print(3, end='\n')
				print(1, 1, l[0] - 1, end='\n')
			else:
				print(2, end='\n')
				print(1, 1, end='\n')
		else:
			l1 = []
			for j in range(n - 3):
				l1.append(l[j])
			if l[n - 2] != 1:
				l1.append(l[n - 3])
				l1.append(l[n - 2] - 1)
				l1.append(1)
				l1.append(1)
			else:
				l1.append(l[n - 3] + 1)
				l1.append(1)
			if l[n - 1] != 1:
				l1.append(l[n - 1] - 1)
			print(len(l1), end='\n')
			for j in l1:
				print(j, end=' ')
			print(end='\n')
	elif n == 2:
		if l[0] - 1 != 0:
			print(3, end='\n')
			print(1, l[1] + 1, l[0] - 1, end='\n')
		else:
			print(2, end='\n')
			print(1, l[1] + 1, end='\n')
	else:
		l1 = []
		for j in range(n - 4):
			l1.append(l[j])
		if l[n - 3] != 1:
			l1.append(l[n - 4])
			l1.append(l[n - 3] - 1)
			l1.append(1)
			l1.append(l[n - 1] + 1)
		else:
			l1.append(l[n - 4] + 1)
			l1.append(l[n - 1] + 1)
		if l[n - 2] != 1:
			l1.append(l[n - 2] - 1)
		print(len(l1), end='\n')
		for j in l1:
			print(j, end=' ')
		print(end='\n')


for T in range(int(input())):
	(n, A) = (int(input()), list(map(int, input().split())))
	if n & 1:
		A.append(0)
	if len(A) < 4:
		A = [0, 1] + A
	C = A[:-4]
	if A[-3] > 1:
		C.extend([A[-4], A[-3] - 1, 1])
	else:
		C.extend([A[-4] + 1])
	C.append(A[-1] + 1)
	if A[-2] > 1:
		C.append(A[-2] - 1)
	print(len(C))
	print(' '.join(map(str, C)))


def _remove_zeros(array):
	j = max(0, len(array) - 5)
	while j < len(array):
		if array[j] != 0:
			j += 1
			continue
		if j == 0:
			array = array[2:]
			continue
		if j == len(array) - 1:
			array.pop()
			continue
		array[j - 1:j + 2] = [array[j - 1] + array[j + 1]]

def next_value(array):
	if array is None:
		raise TypeError('None array')
	if len(array) == 0:
		raise ValueError('Empty array')
	elif len(array) == 2 and array[0] == 0:
		raise ValueError('The input is equivalent to zero')
	if len(array) % 2 == 1:
		if len(array) > 1:
			array[-2] -= 1
		array[-1:] = [1, 1, array[-1] - 1]
	else:
		if len(array) > 2:
			array[-3] -= 1
		array[-2:] = [1, 1 + array[-1], array[-2] - 1]
	_remove_zeros(array)
	return array
n = int(input().strip())
for _ in range(n):
	int(input().strip())
	array = list(map(int, input().strip().split()))
	result = next_value(array)
	print(len(result))
	print(' '.join(map(str, result)))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()[:n]))
	ones = 0
	if n == 1:
		a[0] -= 1
		if a[0] == 0:
			a.pop()
		a.insert(0, 1)
		a.insert(0, 1)
	elif n == 2:
		a[0] -= 1
		a[1] += 1
		(a[0], a[1]) = (a[1], a[0])
		if a[1] == 0:
			a.pop()
		a.insert(0, 1)
	elif n % 2 == 0:
		ones = n - 2
		if a[ones] == 1:
			if a[ones - 1] == 1:
				a[ones - 2] += 1
				a[ones + 1] += 1
				a.pop(ones - 1)
				a.pop(ones - 1)
			else:
				a[ones - 1] -= 1
				a[ones + 1] += 1
		elif a[ones - 1] == 1:
			a[ones - 2] += 1
			a[ones] -= 1
			a[ones + 1] += 1
			(a[ones], a[ones + 1]) = (a[ones + 1], a[ones])
			a.pop(ones - 1)
		else:
			a[ones - 1] -= 1
			a[ones] -= 1
			a[ones + 1] += 1
			(a[ones], a[ones + 1]) = (a[ones + 1], a[ones])
			a.insert(ones, 1)
	else:
		ones = n - 1
		if a[ones] == 1:
			if a[ones - 1] == 1:
				a[ones - 2] += 1
				a.pop(ones)
			else:
				a[ones - 1] -= 1
				a.append(1)
		elif a[ones - 1] == 1:
			a[ones] -= 1
			a[ones - 2] += 1
		else:
			a[ones] -= 1
			a[ones - 1] -= 1
			a.insert(ones, 1)
			a.insert(ones, 1)
	print(len(a))
	print(' '.join((str(x) for x in a)))


t = int(input().strip())
for tt in range(t):
	n = int(input().strip())
	a = [int(_) for _ in input().strip().split()]
	if n == 1:
		r = [1] + [1]
		if a[0] > 1:
			r += [a[0] - 1]
	elif n == 2:
		r = [1] + [1 + a[1]]
		if a[0] > 1:
			r += [a[0] - 1]
	else:
		p = n - 1 >> 1 << 1
		r = a[0:p - 2]
		if a[p - 1] == 1:
			r += [a[p - 2] + 1] + [1]
		else:
			r += [a[p - 2]] + [a[p - 1] - 1] + [1] + [1]
		if n & 1:
			if a[p] > 1:
				r += [a[p] - 1]
		else:
			z = a[n - 1]
			r[-1] += z
			if a[p] > 1:
				r += [a[p] - 1]
	print(len(r))
	print(' '.join((str(_) for _ in r)))


t = int(input().strip())
for _ in range(t):
	n = int(input())
	a = [int(num) for num in input().strip().split()]
	if n % 2 == 1:
		if n == 1:
			c = [1, 1]
		elif a[n - 2] > 1:
			c = a[:max(0, n - 2)]
			c += [a[n - 2] - 1, 1, 1]
		else:
			c = a[:max(0, n - 3)]
			c += [a[n - 3] + 1, 1]
		if a[n - 1] > 1:
			c += [a[n - 1] - 1]
	else:
		if n == 2:
			c = [1, a[n - 1] + 1]
		elif a[n - 3] > 1:
			c = a[:max(0, n - 3)]
			c += [a[n - 3] - 1, 1, a[n - 1] + 1]
		else:
			c = a[:max(0, n - 4)]
			c += [a[n - 4] + 1, a[n - 3] + a[n - 1]]
		if a[n - 2] > 1:
			c += [a[n - 2] - 1]
	print(len(c))
	for e in c[:-1]:
		print(e, end=' ')
	print(c[-1])


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n % 2 == 1:
		if n == 1:
			arr = [1, 1, arr[0] - 1]
		elif arr[-2] == 1:
			arr = arr[:-3] + [arr[-3] + 1, 1, arr[-1] - 1]
		else:
			arr = arr[:-2] + [arr[-2] - 1, 1, 1, arr[-1] - 1]
		if arr[-1] == 0:
			arr = arr[:-1]
	elif n == 2:
		if arr[0] == 1:
			arr[1] += 1
		else:
			arr = [1, arr[1] + 1, arr[0] - 1]
	elif arr[-2] == 1 and arr[-3] == 1:
		arr = arr[:-4] + [arr[-4] + 1, arr[-3] + arr[-1]]
	elif arr[-2] == 1:
		arr = arr[:-3] + [arr[-3] - 1, 1, 1 + arr[-1]]
	elif arr[-3] == 1:
		arr = arr[:-4] + [arr[-4] + 1, arr[-3] + arr[-1], arr[-2] - 1]
	else:
		arr = arr[:-3] + [arr[-3] - 1, 1, 1 + arr[-1], arr[-2] - 1]
	print(len(arr))
	print(' '.join([str(x) for x in arr]))


for _ in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().strip().split()]
	if n == 1:
		A.append(1)
		A.append(A[0] - 1)
		A[0] = 1
	elif n == 2:
		A.append(A[0] - 1)
		A[1] += 1
		A[0] = 1
	else:
		if n % 2:
			A.append(0)
		if A[-3] == 1:
			A[-2] -= 1
			A[-4] += 1
			A[-3] += A[-1]
			del A[-1]
		else:
			A[-3] -= 1
			A.append(A[-2] - 1)
			A[-2] += 1
			A[-3] = 1
	if A[-1] == 0:
		del A[-1]
	print(len(A))
	print(' '.join(map(str, A)))


import sys
T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	A = [int(a) for a in input().strip().split(' ')]
	if N > 2 and N % 2 == 1:
		if A[-2] > 1:
			new_N = N + 2
			C = A[:-2] + [A[-2] - 1, 1, 1, A[-1] - 1]
			if A[-1] == 1:
				new_N -= 1
				C = C[:-1]
		elif A[-1] > 1:
			new_N = N
			C = A[:-3] + [A[-3] + 1, 1, A[-1] - 1]
		else:
			new_N = N - 1
			C = A[:-3] + [A[-3] + 1, 1]
	elif N > 2 and N % 2 == 0:
		if A[-3] > 1:
			new_N = N + 1
			C = A[:-3] + [A[-3] - 1, 1, A[-1] + 1, A[-2] - 1]
		else:
			new_N = N - 1
			C = A[:-4] + [A[-4] + 1, A[-1] + 1, A[-2] - 1]
	elif N == 2:
		new_N = 3
		C = [1, A[1] + 1, A[0] - 1]
	elif N == 1:
		new_N = 3
		C = [1, 1, A[0] + -1]
	if C[-1] == 0:
		new_N -= 1
		C = C[:-1]
	C = [str(c) for c in C]
	print(new_N)
	print(' '.join(C))


class RLE_list:

	def __init__(self, n, l):
		self.n = n
		self.l = l
		self.incremet()

	def reduce_cell(self, ind):
		self.l[ind] -= 1

	def clear_zeros(self):
		l = [0] + self.l
		n = self.n + 1
		ind = 1
		while ind < n - 1:
			if l[ind] == 0:
				l[ind - 1] += l[ind + 1]
				del l[ind + 1]
				del l[ind]
				n -= 2
			else:
				ind += 1
		if l[n - 1] == 0:
			del l[n - 1]
			n -= 1
		del l[0]
		self.l = l
		self.n = n - 1

	def get_last_ones_ind(self):
		return (self.n - 1) * (1 - (self.n - 1) % 2) + (self.n - 2) * ((self.n - 1) % 2)

	def incremet(self):
		ind = self.get_last_ones_ind()
		l = self.l[:ind] + [0, 0] + self.l[ind:] + [0, 0]
		ind += 2
		l[ind - 2] += 1
		l[ind + 2] += l[ind] - 1
		l[ind] = 0
		if ind > 2:
			l[ind - 3] -= 1
		l[ind - 1] += 1
		self.l = l
		self.n += 4
		self.clear_zeros()
tc = range(int(input().strip()))
for _ in tc:
	N = int(input().strip())
	L = list(map(int, input().strip().split(' ')))
	rlel = RLE_list(N, L)
	print(len(rlel.l))
	print(' '.join(map(str, rlel.l)))


def clean(a):
	i = 0
	while i < len(a):
		if a[i][0] == 0:
			del a[i]
		else:
			i += 1
	i = 0
	while i < len(a) - 1:
		if a[i][1] == a[i + 1][1]:
			a[i][0] += a[i + 1][0]
			del a[i + 1]
		else:
			i += 1
	return a
nTestCases = int(input().strip())
for _ in range(nTestCases):
	input()
	values = [int(x) for x in input().strip().split()]
	bit = 1
	for i in range(len(values)):
		values[i] = [values[i], bit]
		bit ^= 1
	lastZero = None
	if len(values) % 2 == 0:
		lastZero = values.pop()
	if len(values) == 1:
		a = [[1, 1], [1, 0], [values[0][0] - 1, 1]]
	else:
		a = values[:-2] + [[values[-2][0] - 1, 0], [1, 1], [1, 0], [values[-1][0] - 1, 1]]
	if lastZero:
		a.append(lastZero)
		if len(a) > 1:
			a[-2:] = a[-1:-3:-1]
	a = clean(a)
	print(len(a))
	for (x, bit) in a:
		print(x, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1:
		if a[0] == 1:
			a = [1, 1]
		else:
			a = [1, 1, a[0] - 1]
	elif n == 2:
		if a[0] == 1:
			a = [a[0], a[1] + 1]
		else:
			a = [1, a[1] + 1, a[0] - 1]
	elif n % 2 == 1:
		if a[-2] == 1:
			a[-3:] = [a[-3] + 1, 1, a[-1] - 1]
		else:
			a[-2:] = [a[-2] - 1, 1, 1, a[-1] - 1]
	elif a[-3] == 1:
		a[-4:] = [a[-4] + 1, a[-1] + 1, a[-2] - 1]
	else:
		a[-3:] = [a[-3] - 1, 1, a[-1] + 1, a[-2] - 1]
	if a[-1] == 0:
		del a[-1]
	print(len(a))
	print(*a)


def test(B):
	if B[-3] > 1:
		if B[-2] > 1:
			return (1, B[:-3] + [B[-3] - 1, 1, B[-1] + 1, B[-2] - 1])
		else:
			return (0, B[:-3] + [B[-3] - 1, 1, B[-1] + 1])
	elif B[-2] > 1:
		return (-1, B[:-4] + [B[-4] + 1, B[-1] + 1, B[-2] - 1])
	else:
		return (-2, B[:-4] + [B[-4] + 1, B[-1] + 1])
for _ in range(int(input())):
	L = int(input())
	A = list(map(int, input().split()))
	if L == 1:
		if A == [1]:
			print(2)
			print('1 1')
		else:
			print(3)
			print(' '.join(['1', '1', str(A[0] - 1)]))
	elif L == 2:
		if A[0] == 1:
			print(2)
			print('1', A[1] + 1)
		else:
			print(3)
			print('1', A[1] + 1, A[0] - 1)
	else:
		if L % 2:
			A.append(0)
			L += 1
		(cL, C) = test(A)
		print(L + cL)
		print(' '.join(map(str, C)))


def foo(lst):
	m = len(lst)
	i = m - 1
	i -= i % 2
	if i > 0:
		if lst[i - 1] == 1:
			ris = lst[:i - 2] + [lst[i - 2] + 1]
		else:
			ris = lst[:i - 1] + [lst[i - 1] - 1, 1]
	else:
		ris = [1]
	if i < m - 1:
		ris.append(lst[-1] + 1)
	else:
		ris.append(1)
	if lst[i] > 1:
		ris.append(lst[i] - 1)
	return ris
N = int(input().strip())
for i in range(N):
	n = int(input().strip())
	lst = [int(x) for x in input().strip().split(' ')]
	lst1 = foo(lst)
	print(len(lst1))
	print(' '.join([str(x) for x in lst1]))


T = int(input().strip())
N = []
S = []
for t in range(0, T):
	n = int(input().strip())
	seq = list(map(lambda x: int(x), input().strip().split(' ')))
	N.append(n)
	S.append(seq)

def extzero(seq_):
	ones = 0
	n = len(seq_)
	for j in range(0, n, 2):
		ones += seq_[j]
	zeros = 0
	for j in range(1, n, 2):
		zeros += seq_[j]
	if ones == 1:
		return [1, zeros + 1]
	return [1, zeros + 1, ones - 1]
for t in range(0, T):
	n = N[t]
	seq = S[t]
	ones = 0
	if n % 2 == 0:
		i = n - 2
	else:
		i = n - 1
	end_seq = seq[i - n:]
	start_seq = seq[:i - n]
	end_seq = extzero(end_seq)
	if len(start_seq) > 0:
		if start_seq[-1] == 1:
			end_seq[0] += start_seq[-2]
			start_seq = start_seq[:-2]
		else:
			start_seq[-1] -= 1
	start_seq.extend(end_seq)
	print(len(start_seq))
	print(str(start_seq).strip('[]').replace(',', ''))


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	arr = [int(n) for n in input().split()]
	if len(arr) % 2 == 0:
		arr[n - 1] += 1
		temp = arr[n - 2] - 1
		if temp != 0:
			arr[n - 2] = 1
			if n > 3:
				arr[n - 3] -= 1
			arr.extend([temp])
		elif n > 3:
			arr[n - 3] -= 1
	elif n == 1:
		arr[n - 1] -= 1
		arr.insert(n - 1, 1)
		arr.insert(n - 1, 1)
	else:
		arr[n - 1] -= 1
		arr[n - 2] -= 1
		arr.insert(n - 1, 1)
		arr.insert(n - 1, 1)
	if arr[len(arr) - 1] == 0:
		del arr[len(arr) - 1]
	for x in range(len(arr)):
		if arr[x] == 0:
			arr[x - 1] += arr[x + 1]
			del arr[x + 1]
			del arr[x]
			break
	print(len(arr))
	print(*arr)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [0, 1] + list(map(int, input().split()))
	l1 = N + 1 & -2
	XL = A[:l1 - 1]
	X = [A[l1 - 1] - 1, 1, 1, A[l1] - 1]
	XR = A[l1 + 1:]
	if len(XR) and X[3]:
		X[2] += XR[0]
		XR = []
	elif len(XR):
		XR[0] += X[2]
		X = X[:2]
	elif X[3] == 0:
		X = X[:3]
	if X[0] == 0:
		XL[-1] += 1
		X = X[2:]
	if not XL[0]:
		XL = XL[2:]
	C = XL + X + XR
	print(len(C))
	print(' '.join(map(str, C)))


class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))


test_cases = int(input())
for _ in range(test_cases):
	(n, A) = (int(input()), list(map(int, input().split())))
	last_ones_set = -1 - int(n % 2 == 0)
	A[last_ones_set] -= 1
	if n + last_ones_set - 1 >= 0:
		A[last_ones_set - 1] -= 1
	if A[last_ones_set] >= 1 and last_ones_set == -2:
		A[last_ones_set:] = [1, 1 + A[last_ones_set + 1], A[last_ones_set]]
	else:
		A[last_ones_set:] = [1, 1] + A[last_ones_set:]
	if A[-1] == 0:
		A.pop()
	for (i, num) in enumerate(A):
		if num == 0:
			A[i - 1] += A[i + 1]
			A.pop(i)
			A.pop(i)
	print(len(A))
	print(*A)


def zlfill(arr):
	zeros = sum(arr[::2])
	ones = sum(arr[1::2])
	return [zeros, ones]

def zstrip(arr):
	if not arr:
		return []
	elif 0 in arr:
		idx = arr.index(0)
		if idx == len(arr) - 1:
			return arr[:-1]
		mod_arr = arr[:idx] + zstrip(arr[idx + 2:])
		mod_arr[idx - 1] += arr[idx + 1]
		return mod_arr
	else:
		return arr
T = int(input())
for i in range(T):
	n = int(input())
	arr_A = list(map(int, input().strip().split(' ')))
	C = []
	if n == 1:
		ones = arr_A[0]
		C = zstrip([1, 1, ones - 1])
	elif n == 2:
		(ones, zeros) = arr_A
		C = zstrip([1, zeros + 1, ones - 1])
	else:
		last_zero = n - 3 if n % 2 == 0 else n - 2
		arr_swap = arr_A[:last_zero + 1] + [1, 1] + arr_A[last_zero + 1:]
		arr_swap[last_zero] -= 1
		arr_swap[last_zero + 3] -= 1
		arr_C = arr_swap[:last_zero + 2] + zlfill(arr_swap[last_zero + 2:])
		C = zstrip(arr_C)
	print(len(C))
	print(' '.join([str(x) for x in C]))


t = int(input())
for ti in range(t):
	n = int(input())
	a = [int(s) for s in input().split()]
	if n == 1:
		if a[0] == 1:
			n1 = n + 1
			a1 = [1, 1]
		else:
			a1 = [1, 1, a[0] - 1]
			n1 = n + 2
	elif n == 2:
		if a[0] == 1:
			n1 = n
			a1 = [1, a[1] + 1]
		else:
			a1 = [1, a[1] + 1, a[0] - 1]
			n1 = n + 1
	elif n % 2 != 0:
		if a[-2] == 1 and a[-1] == 1:
			n1 = n - 1
			a1 = a[:-3] + [a[-3] + 1, 1]
		elif a[-2] == 1:
			a1 = a[:-3] + [a[-3] + 1, 1, a[-1] - 1]
			n1 = n
		elif a[-1] == 1:
			a1 = a[:-2] + [a[-2] - 1, 1, 1]
			n1 = n + 1
		else:
			a1 = a[:-2] + [a[-2] - 1, 1, 1, a[-1] - 1]
			n1 = n + 2
	elif a[-3] == 1 and a[-2] == 1:
		n1 = n - 2
		a1 = a[:-4] + [a[-4] + 1, a[-1] + 1]
	elif a[-3] == 1:
		n1 = n - 1
		a1 = a[:-4] + [a[-4] + 1, a[-1] + 1, a[-2] - 1]
	elif a[-2] == 1:
		n1 = n
		a1 = a[:-3] + [a[-3] - 1, 1, a[-1] + 1]
	else:
		a1 = a[:-3] + [a[-3] - 1, 1, a[-1] + 1, a[-2] - 1]
		n1 = n + 1
	print(n1)
	for i in a1:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	(n, arr) = (int(input()), list(map(int, input().split())))
	if n == 1:
		barr = [1, 1, arr[0] - 1]
	elif n == 2:
		barr = [1, arr[1] + 1, arr[0] - 1]
	elif n % 2 == 1:
		barr = [arr[i] for i in range(n - 2)]
		if arr[-2] == 1:
			barr[-1] += 1
		else:
			barr.append(arr[-2] - 1)
			barr.append(1)
		barr.append(1)
		barr.append(arr[-1] - 1)
	else:
		barr = [arr[i] for i in range(n - 3)]
		if arr[-3] == 1:
			barr[-1] += 1
		else:
			barr.append(arr[-3] - 1)
			barr.append(1)
		if barr[-1] == 0:
			barr = barr[:-1]
		barr.append(1 + arr[-1])
		barr.append(arr[-2] - 1)
	if barr[-1] == 0:
		barr = barr[:-1]
	print(len(barr))
	print(*barr)


def is_odd(x):
	return int(x) % 2

def print_list(a):
	s = ''
	for x in a:
		s = s + str(x) + ' '
	s = s[:-1]
	print(s)
n = int(input().strip())
for i in range(0, n):
	k = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	l = k
	if l == 1:
		if a[0] - 1 > 0:
			print(3)
			print(1, 1, a[0] - 1)
		else:
			print(2)
			print(1, 1)
	if l == 2:
		if a[0] - 1 > 0:
			print(3)
			print(1, 1 + a[1], a[0] - 1)
		else:
			print(2)
			print(1, 1 + a[1])
	if l > 2:
		if is_odd(l):
			x = a[l - 2]
			y = a[l - 1]
			a = a[:-2]
			if x - 1 > 0:
				a.append(x - 1)
				a.append(1)
			else:
				a[len(a) - 1] += 1
			a.append(1)
			if y - 1 > 0:
				a.append(y - 1)
		else:
			x = a[l - 3]
			y = a[l - 2]
			z = a[l - 1]
			a = a[:-3]
			if x - 1 > 0:
				a.append(x - 1)
				a.append(1)
			else:
				a[len(a) - 1] += 1
			a.append(1 + z)
			if y - 1 > 0:
				a.append(y - 1)
		print(len(a))
		print_list(a)


t = int(input().strip())
while t > 0:
	t -= 1
	n = int(input().strip())
	vals = [int(x) for x in input().strip().split()]
	if n == 1:
		if vals[0] == 1:
			print(2)
			print(1, vals[0])
		else:
			print(3)
			print(1, 1, vals[0] - 1)
		continue
	if n & 1:
		if vals[-2] == 1:
			if vals[-1] == 1:
				print(n - 1)
				for val in vals[:-3]:
					print(val, end=' ')
				print(vals[-3] + 1, 1)
			else:
				print(n)
				for val in vals[:-3]:
					print(val, end=' ')
				print(vals[-3] + 1, 1, vals[-1] - 1)
		elif vals[-1] == 1:
			print(n + 1)
			for val in vals[:-2]:
				print(val, end=' ')
			print(vals[-2] - 1, 1, 1)
		else:
			print(n + 2)
			for val in vals[:-2]:
				print(val, end=' ')
			print(vals[-2] - 1, 1, 1, vals[-1] - 1)
	else:
		if n == 2:
			if vals[0] == 1:
				print(2)
				print(1, vals[-1] + 1)
			else:
				print(3)
				print(1, vals[1] + 1, vals[0] - 1)
			continue
		if vals[-3] == 1:
			if vals[-2] == 1:
				print(n - 2)
				for val in vals[:-4]:
					print(val, end=' ')
				print(vals[-4] + 1, vals[-1] + 1)
			else:
				print(n - 1)
				for val in vals[:-4]:
					print(val, end=' ')
				print(vals[-4] + 1, vals[-1] + 1, vals[-2] - 1)
		elif vals[-2] == 1:
			print(n)
			for val in vals[:-3]:
				print(val, end=' ')
			print(vals[-3] - 1, 1, vals[-1] + 1)
		else:
			print(n + 1)
			for val in vals[:-3]:
				print(val, end=' ')
			print(vals[-3] - 1, 1, vals[-1] + 1, vals[-2] - 1)


n = int(input().strip())
for i in range(n):
	x = input().strip()
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	if len(a) == 1:
		b = [1, 1, a[0] - 1]
	elif len(a) == 2:
		b = [1, 1 + a[-1], a[0] - 1]
	elif len(a) % 2 == 0:
		b = a[:-3] + [a[-3] - 1, 1, a[-1] + 1, a[-2] - 1]
	else:
		b = a[:-2] + [a[-2] - 1, 1, 1, a[-1] - 1]
	c = []
	i = 0
	while i < len(b):
		if b[i] > 0:
			c.append(b[i])
		elif i < len(b) - 1:
			c[-1] += b[i + 1]
			i += 1
		i += 1
	print(len(c))
	print(' '.join(map(str, c)))


import sys
T = int(input().strip())
for _ in range(T):
	binary_A = []
	n = int(input().strip())
	A = list(map(int, input().strip().split()))
	if n > 1:
		if n % 2 == 0:
			if n >= 4:
				if A[n - 3] == 1:
					if A[n - 2] != 1:
						A[n - 2] -= 1
						A[n - 4] += 1
						A[n - 3] += A[n - 1]
						del A[n - 1]
					else:
						A[n - 4] += 1
						A[n - 3] += A[n - 1]
						del A[n - 2]
						del A[n - 2]
				else:
					A[n - 3] -= 1
					A[n - 2] -= 1
					for _ in range(2):
						A.insert(n - 2, 1)
					A[n - 1] += A[n + 1]
					del A[n + 1]
			elif A[n - 2] == 1:
				A[n - 1] += 1
			else:
				A = [1, A[n - 1] + 1, A[n - 2] - 1]
		elif A[n - 2] == 1:
			if A[n - 1] != 1:
				A[n - 1] -= 1
				A[n - 3] += 1
			else:
				A[n - 3] += 1
				del A[n - 1]
		else:
			A[n - 2] -= 1
			A[n - 1] -= 1
			for _ in range(2):
				A.insert(n - 1, 1)
	else:
		A[0] -= 1
		for _ in range(2):
			A.insert(0, 1)
	if A[-1] == 0:
		del A[-1]
	print(len(A))
	print(' '.join((str(x) for x in A)))


def main():
	t = int(input())
	for xx in range(0, t):
		n = int(input())
		a = [int(x) for x in input().split()]
		if n == 1:
			if a[0] == 1:
				print('2\n1 1')
			else:
				print('3\n1 1 {}'.format(a[0] - 1))
		elif n == 2:
			if a[-2] == 1:
				print('2\n1 {}'.format(a[-1] + 1))
			else:
				print('3\n1 {} {}'.format(a[-1] + 1, a[-2] - 1))
		elif n % 2 == 1:
			a[-2] -= 1
			aa = a[-1]
			if a[-2] == 0:
				a[-3] += 1
				a = a[:-2]
			else:
				a[-1] = 1
			if aa != 1:
				a += [1, aa - 1]
			else:
				a += [1]
			print(len(a), end='\n')
			for x in a:
				print(x, end=' ')
			print()
		else:
			if a[-2] == 1:
				a[-3] -= 1
				a[-1] += 1
				if a[-3] == 0:
					a = a[:-3] + a[-2:]
					a[-3] += 1
					a = a[:-2] + a[-1:]
			else:
				e1 = a[-1]
				e2 = a[-2]
				e3 = a[-3]
				a = a[0:-3]
				if e3 != 1:
					a += [e3 - 1]
					a += [1]
				else:
					a[-1] += 1
				a += [e1 + 1]
				if e2 != 1:
					a += [e2 - 1]
			print(len(a), end='\n')
			for x in a:
				print(x, end=' ')
			print()
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = [1000] + l
	if n % 2:
		l = l[:-2] + [l[-2] - 1, 1, 1, l[-1] - 1]
	else:
		l = l[:-3] + [l[-3] - 1, 1, l[-1] + 1, l[-2] - 1]
	while 1:
		for i in range(1, len(l)):
			if l[i] == 0:
				if i == len(l) - 1:
					l = l[:-1]
				else:
					l = l[:i - 1] + [l[i - 1] + l[i + 1]] + l[i + 2:]
				break
		else:
			break
	print(len(l) - 1)
	print(' '.join(map(str, l[1:])))


n = int(input())
for i in range(n):
	n1 = int(input())
	arr = list(map(int, input().split()))
	if n1 == 1:
		arr.insert(1, 1)
		if arr[0] > 1:
			arr.insert(2, arr[0] - 1)
			arr[0] = 1
	elif n1 == 2:
		if arr[0] > 1:
			arr.insert(2, arr[0] - 1)
			arr[1] = arr[1] + 1
			arr[0] = 1
		else:
			arr[1] = arr[1] + 1
	elif n1 % 2 == 0:
		if arr[-3] > 1:
			arr[-3] = arr[-3] - 1
			if arr[-2] > 1:
				arr.insert(-2, 1)
				arr[-1] = arr[-1] + 1
				a = arr[-1]
				arr[-1] = arr[-2] - 1
				arr[-2] = a
			else:
				arr[-1] = arr[-1] + 1
		elif arr[-2] > 1:
			arr[-4] = arr[-4] + 1
			arr[-2] = arr[-2] - 1
			arr[-3] = arr[-3] + arr[-1]
			arr.pop()
		else:
			arr[-4] = arr[-4] + 1
			arr[-3] = arr[-3] + arr[-1]
			arr.pop()
			arr.pop()
	elif arr[-1] > 1:
		arr[-1] = arr[-1] - 1
		if arr[-2] > 1:
			arr[-2] = arr[-2] - 1
			arr.insert(-1, 1)
			arr.insert(-1, 1)
		else:
			arr[-3] = arr[-3] + 1
	else:
		arr.pop()
		if arr[-1] > 1:
			arr[-1] = arr[-1] - 1
			arr.append(1)
			arr.append(1)
		else:
			arr[-2] = arr[-2] + 1
	print(len(arr))
	print(*arr, sep=' ')


from math import *
from pprint import *
from bisect import bisect
from itertools import groupby, chain, combinations, permutations
from heapq import *
from collections import deque, Counter
from functools import cmp_to_key, reduce

def handle(values):
	if len(values) == 1:
		return [1, 1, values[0] - 1] if values[0] > 1 else [1, 1]
	last0 = len(values) - 2 if len(values) % 2 else len(values) - 1
	zeros = values[last0]
	start = values[:-2] if len(values) % 2 else values[:-1]
	after = 0 if not len(values) % 2 else values[-1]
	if not after:
		if len(start) > 1:
			return [*start[:-2], start[-2] - 1, 1, zeros + 1, start[-1] - 1]
		else:
			return [1, zeros + 1, start[-1] - 1]
	elif zeros == 1:
		return [*start[:-1], start[-1] + 1, zeros, after - 1]
	else:
		return [*start[:-1], start[-1], zeros - 1, 1, 1, after - 1]

def cleanup(res):
	cleaned = []
	cleaned.append(res[0])
	i = 1
	while i < len(res):
		curr = res[i]
		if curr == 0:
			i += 1
			if i < len(res):
				cleaned[-1] += res[i]
		else:
			cleaned.append(curr)
		i += 1
	return cleaned

def run():
	T = int(input())
	for _ in range(T):
		_ = int(input())
		values = [int(i) for i in input().split()]
		res = cleanup(handle(values))
		print(len(res))
		print(' '.join((str(i) for i in res)))
run()


import sys

def solve(aa):
	print('aa=%s' % aa, file=sys.stderr)
	i = len(aa) - 1
	if i % 2 == 1:
		i -= 1
	print('i=%d' % i, file=sys.stderr)
	if i == 0:
		cache = [1, 1] + [aa[i] - 1] + aa[i + 1:]
	else:
		cache = aa[:i - 1] + [aa[i - 1] - 1] + [1, 1] + [aa[i] - 1] + aa[i + 1:]
	print('cache=%s' % cache, file=sys.stderr)
	if i == len(aa) - 2:
		(ones, zeros) = cache[-2:]
		print('ones=%d zeros=%d' % (ones, zeros), file=sys.stderr)
		cache = cache[:-2] + [0, zeros, ones]
		print('cache=%s' % cache, file=sys.stderr)
	(new_cache, r) = ([], 0)
	for i in range(0, len(cache) - 1, 2):
		(ones, zeros) = cache[i:i + 2]
		if zeros == 0:
			r += ones
		else:
			new_cache.append(ones + r)
			new_cache.append(zeros)
			r = 0
	if len(cache) % 2 == 1:
		v = cache[-1] + r
		if v > 0:
			new_cache.append(v)
	cache = new_cache
	print('cache=%s' % cache, file=sys.stderr)
	(new_cache, r) = (cache[:1], 0)
	for i in range(1, len(cache) - 1, 2):
		(zeros, ones) = cache[i:i + 2]
		if ones == 0:
			r += zeros
		else:
			new_cache.append(zeros + r)
			new_cache.append(ones)
			r = 0
	if len(cache) % 2 == 0:
		v = cache[-1] + r
		if v > 0:
			new_cache.append(v)
	cache = new_cache
	print('cache=%s' % cache, file=sys.stderr)
	return cache
t = int(input())
for _ in range(t):
	_ = int(input())
	aa = list(map(int, input().split()))
	bb = solve(aa)
	print('------', file=sys.stderr)
	print(len(bb))
	print(' '.join(map(str, bb)))


def findC(ar):
	N = len(ar)
	if N == 1:
		if ar[0] > 1:
			return [1, 1, ar[0] - 1]
		else:
			return [1, 1]
	if N == 2:
		if ar[0] > 1:
			return [1, ar[1] + 1, ar[0] - 1]
		else:
			return [ar[0], ar[1] + 1]
	if N % 2 == 1:
		zeros = ar[-2]
		ones = ar[-1]
		newZeros = zeros - 1
		newOnes = ones - 1
		if newZeros == 0 and newOnes == 0:
			del ar[-1]
			ar[-2] += 1
			return ar
		if newZeros == 0 and newOnes > 0:
			ar[-3] += 1
			ar[-1] -= 1
			return ar
		if newZeros > 0 and newOnes == 0:
			ar[-2] -= 1
			ar[-1] = 1
			ar.append(1)
			return ar
		ar[-2] = newZeros
		ar[-1] = 1
		ar.append(1)
		ar.append(newOnes)
		return ar
	else:
		if ar[-3] > 1:
			ar[-3] -= 1
			ones = ar[-2] - 1
			zeros = ar[-1] + 1
			ar[-2] = 1
			ar[-1] = zeros
			if ones > 0:
				ar.append(ones)
			return ar
		ar[-4] += 1
		ar[-3] = ar[-1] + 1
		ones = ar[-2] - 1
		del ar[-1]
		if ones > 0:
			ar[-1] = ones
		else:
			del ar[-1]
		return ar
T = int(input().strip())
for t in range(T):
	n = int(input().strip())
	ar = list(map(int, input().strip().split(' ')))
	ar = findC(ar)
	print(len(ar))
	sOut = str(ar[0])
	for i in range(1, len(ar)):
		sOut += ' ' + str(ar[i])
	print(sOut)


import sys

def main():
	num_test_cases = 0
	start_test_case = False
	size_test_case = 0
	test_case = []
	for line in sys.stdin.readlines():
		line = line.rstrip()
		if num_test_cases == 0:
			num_test_cases = line
		elif not start_test_case:
			size_test_case = int(line)
			start_test_case = True
		else:
			test_case = line.split(' ')
			for i in range(len(test_case)):
				test_case[i] = int(test_case[i])
			if size_test_case == 1:
				test_case.append(1)
			elif size_test_case == 2:
				test_case[1] = test_case[1] + 1
			else:
				zero_index = size_test_case - 2
				one_index = size_test_case - 1
				if size_test_case % 2 == 0:
					zero_index = zero_index - 1
					one_index = one_index - 1
				test_case[zero_index] = test_case[zero_index] - 1
				test_case[one_index] = test_case[one_index] - 1
				if test_case[zero_index] >= 1:
					test_case.insert(one_index, 1)
					one_index = one_index + 1
				else:
					test_case[zero_index - 1] = test_case[zero_index - 1] + 1
					test_case.pop(zero_index)
					one_index = one_index - 1
				if test_case[one_index] >= 1:
					test_case.insert(one_index, 1)
					one_index = one_index + 1
				else:
					if one_index + 1 < len(test_case):
						test_case[one_index + 1] = test_case[one_index + 1] + 1
					else:
						test_case.append(1)
					test_case.pop(one_index)
				if size_test_case % 2 == 0 and (zero_index + one_index) % 2 != 0:
					current_index = one_index - 1
					consolidated_zero_count = 0
					consolidated_one_count = 0
					while current_index < len(test_case):
						if current_index % 2 == 0:
							consolidated_one_count = consolidated_one_count + test_case[current_index]
						else:
							consolidated_zero_count = consolidated_zero_count + test_case[current_index]
						current_index = current_index + 1
					test_case[one_index - 1] = consolidated_zero_count
					test_case[one_index] = consolidated_one_count
					current_index = one_index + 1
					while current_index < len(test_case):
						test_case.pop()
			if size_test_case <= 2 and test_case[0] > 1:
				test_case.append(test_case[0] - 1)
				test_case[0] = 1
			print(len(test_case))
			result_string = ''
			for i in range(len(test_case)):
				result_string = result_string + str(test_case[i])
				if i < len(test_case) - 1:
					result_string = result_string + ' '
			print(result_string)
			start_test_case = False
main()


import sys

def solucao(arr):
	for arrA in arr:
		n = len(arrA)
		if n % 2 == 0:
			pos1 = n - 2
			final0 = True
		else:
			pos1 = n - 1
			final0 = False
		if pos1 > 0:
			arrA[pos1 - 1] -= 1
		arrA[pos1] -= 1
		arrA.insert(pos1, 1)
		arrA.insert(pos1, 1)
		n += 2
		if final0:
			arrA[pos1 + 1] += arrA[pos1 + 3]
			del arrA[pos1 + 3]
			n -= 1
		for e in range(arrA.count(0)):
			pos0 = arrA.index(0)
			if pos0 != n - 1:
				arrA[pos0 - 1] += arrA[pos0 + 1]
				del arrA[pos0 + 1]
				n -= 1
			del arrA[pos0]
			n -= 1
		print(n)
		print(' '.join(map(str, arrA)))
t = int(input().strip())
arr = []
for a_i in range(t):
	n = input().strip()
	a_t = list(map(int, input().strip().split(' ')))
	arr.append(a_t)
solucao(arr)


def next_equal_count(a):
	if len(a) == 1:
		if a[0] == 1:
			return [1, 1]
		return [1, 1, a[0] - 1]
	n = len(a)
	last_zero_idx = n // 2 * 2 - 1
	if last_zero_idx < n - 1:
		if a[last_zero_idx] > 1:
			a[last_zero_idx] -= 1
			tmp = a[last_zero_idx + 1]
			a.append(1)
			if tmp > 1:
				a[last_zero_idx + 1] = 1
				a.append(tmp - 1)
		else:
			a[last_zero_idx - 1] += 1
			a[last_zero_idx + 1] -= 1
			if not a[-1]:
				del a[-1]
	elif n > 2:
		if a[last_zero_idx - 2] > 1:
			a[last_zero_idx - 2] -= 1
			a[last_zero_idx] += 1
			tmp = a[last_zero_idx - 1]
			if tmp > 1:
				a[last_zero_idx - 1] = 1
				a.append(tmp - 1)
		else:
			a[last_zero_idx - 3] += 1
			a[last_zero_idx - 2] += a[last_zero_idx]
			a[last_zero_idx - 1] -= 1
			del a[-1]
			if not a[-1]:
				del a[-1]
	elif a[0] == 1:
		a[1] += 1
	else:
		a.append(a[0] - 1)
		a[0] = 1
		a[1] += 1
	return a
t = int(input().strip())
for i in range(t):
	n = input().strip()
	a = list(map(int, input().strip().split()))
	d = next_equal_count(a)
	if not min(d):
		raise Exception('zero in array')
	print(len(d))
	print(' '.join(list(map(str, d))))


class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))


T = int(input())

def compact(A):
	result = []
	i = 1
	while A[i] == 0:
		i += 1
	j = len(A) - 1
	while B[j] == 0:
		j -= 1
	while i <= j:
		if A[i] == 0:
			result[-1] += A[i + 1]
			i += 2
		else:
			result.append(A[i])
			i += 1
	return result
for t0 in range(T):
	n = int(input())
	A = list(map(int, input().split(' ')))
	A = [1] + A + [0]
	index = (n - 1) // 2 * 2 + 1
	B = A[:index - 1] + [A[index - 1] - 1, 1, A[index + 1] + 1, A[index] - 1] + A[index + 2:]
	B = compact(B)
	print(len(B))
	print(' '.join(map(str, B)))


tests = int(input())
for test in range(tests):
	n = int(input())
	A = [int(s) for s in input().split()]
	last3 = A[-3:]
	if n % 2 == 0:
		if n == 2:
			if A[0] == 1:
				print(2)
				print(1, A[1] + 1)
			else:
				print(3)
				print(1, A[1] + 1, A[0] - 1)
		elif last3[0] == 1:
			if last3[1] != 1:
				A[-4] += 1
				print(n - 1)
				print(*A[:-3], 1 + last3[2], last3[1] - 1)
				continue
			else:
				A[-4] += 1
				print(n - 2)
				print(*A[:-3], 1 + last3[2])
		elif last3[1] == 1:
			print(n)
			print(*A[:-3], last3[0] - 1, 1, last3[2] + 1)
		else:
			print(n + 1)
			print(*A[:-3], last3[0] - 1, 1, last3[2] + 1, last3[1] - 1)
	elif n == 1:
		if A[0] == 1:
			print(2)
			print(1, 1)
		else:
			print(3)
			print(1, 1, A[0] - 1)
	elif A[-2] == 1:
		A[-3] += 1
		if A[-1] == 1:
			print(n - 1)
			print(*A[:-2], 1)
		else:
			print(n)
			print(*A[:-2], 1, A[-1] - 1)
	elif A[-1] == 1:
		print(n + 1)
		print(*A[:-2], A[-2] - 1, A[-1], 1)
	else:
		print(n + 2)
		print(*A[:-2], A[-2] - 1, 1, 1, A[-1] - 1)


for _ in range(int(input())):
	(n, data) = (int(input()), [int(x) for x in input().split(' ')])
	if n == 1:
		print('2\n1 1' if data[0] == 1 else '3\n1 1 %d' % (data[0] - 1))
	elif n == 2:
		print('2\n1 %d' % (data[1] + 1) if data[0] == 1 else '3\n1 %d %d' % (data[1] + 1, data[0] - 1))
	else:
		c = n
		rs = ' '.join(map(str, data[0:-3 - (n & 1 ^ 1)]))
		if rs:
			rs += ' '
		ed = data[-3 - (n & 1 ^ 1):]
		if len(ed) == 3:
			ed.append(0)
			c += 1
		ed[1] -= 1
		t = ed[2]
		ed[2] = ed[3] + 1
		ed[3] = t - 1
		ed.insert(2, 1)
		c += 1
		if ed[1] == 0:
			ed = [ed[0] + 1, ed[3], ed[4]]
			c -= 2
		if ed[-1] == 0:
			ed = ed[0:len(ed) - 1]
			c -= 1
		print(c)
		rs += ' '.join(map(str, ed))
		print(rs)


import os
import sys
from itertools import zip_longest as zl

def whatsNext(arr):
	lr_pairs = list(zl(arr[::2], arr[1::2], fillvalue=0))
	if len(lr_pairs) > 1:
		lr_pairs.insert(-1, (1, lr_pairs[-1][1] + 1))
		lr_pairs[-3] = (lr_pairs[-3][0], lr_pairs[-3][1] - 1)
		lr_pairs[-1] = (lr_pairs[-1][0] - 1, 0)
		result = []
		if not (lr_pairs[-3][0] and lr_pairs[-3][1]):
			lr_pairs[-3] = (lr_pairs[-3][0] + lr_pairs[-2][0], lr_pairs[-3][1] + lr_pairs[-2][1])
			del lr_pairs[-2]
		for pair in lr_pairs:
			if pair[0]:
				result.append(pair[0])
			if pair[1]:
				result.append(pair[1])
		return result
	else:
		result = [1, lr_pairs[0][1] + 1, lr_pairs[0][0] - 1]
		if not result[-1]:
			result = list(result[:-1])
		return result
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	res = whatsNext(arr)
	print(len(res))
	print(*res)


for _ in range(int(input().strip())):
	input()
	integers = list(map(int, input().strip().split()))
	if len(integers) > 2:
		if len(integers) % 2 != 0:
			a = integers[-3]
			b = integers[-2]
			c = integers[-1]
			if b > 1 and c > 1:
				integers.pop()
				integers.pop()
				integers.append(b - 1)
				integers.append(1)
				integers.append(1)
				integers.append(c - 1)
			elif b > 1 and c == 1:
				integers.pop()
				integers.pop()
				integers.append(b - 1)
				integers.append(1)
				integers.append(1)
			elif b == 1 and c > 1:
				integers.pop()
				integers.pop()
				integers.pop()
				integers.append(a + 1)
				integers.append(1)
				integers.append(c - 1)
			else:
				integers.pop()
				integers.pop()
				integers.pop()
				integers.append(a + 1)
				integers.append(1)
		else:
			a = integers[-4]
			b = integers[-3]
			c = integers[-2]
			d = integers[-1]
			if b > 1 and c > 1:
				integers.pop()
				integers.pop()
				integers.pop()
				integers.append(b - 1)
				integers.append(1)
				integers.append(d + 1)
				integers.append(c - 1)
			elif b > 1 and c == 1:
				integers.pop()
				integers.pop()
				integers.pop()
				integers.append(b - 1)
				integers.append(1)
				integers.append(d + 1)
			elif b == 1 and c > 1:
				integers.pop()
				integers.pop()
				integers.pop()
				integers.pop()
				integers.append(a + 1)
				integers.append(d + 1)
				integers.append(c - 1)
			else:
				integers.pop()
				integers.pop()
				integers.pop()
				integers.pop()
				integers.append(a + 1)
				integers.append(d + 1)
	elif len(integers) == 2:
		b = integers.pop()
		a = integers.pop()
		if a > 1:
			integers.append(1)
			integers.append(b + 1)
			integers.append(a - 1)
		else:
			integers.append(1)
			integers.append(b + 1)
	else:
		a = integers.pop()
		if a > 1:
			integers.append(1)
			integers.append(1)
			integers.append(a - 1)
		else:
			integers.append(1)
			integers.append(1)
	print(len(integers))
	print(' '.join((str(integer) for integer in integers)))


import os
import sys

def whatsNext(arr):
	odd = len(arr) % 2
	if odd:
		arr.append(0)
	append = []
	i = len(arr) - 4
	append.append(arr[i] if i >= 0 else 0)
	append.append(arr[i + 1] - 1 if i + 1 >= 0 else 0)
	append.append(1)
	append.append(arr[i + 3] + 1)
	append.append(arr[i + 2] - 1)
	length = 5
	index = 0
	while index < length:
		if append[index] == 0:
			if index > 0 and index < length - 1:
				append[index - 1] += append[index + 1]
				append.pop(index)
				length -= 1
			append.pop(index)
			length -= 1
		else:
			index += 1
	if i > 0:
		arr = arr[:i] + append
	else:
		arr = append
	print(len(arr))
	print(' '.join(map(str, arr)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(arr):
	extra_0 = 0
	extra_1 = 0
	add = 0
	pos = 0
	temp = 0
	res = ''
	for i in range(arr_count - 1, -1, -1):
		if i % 2 == 0:
			temp = arr[i] - 1
			if temp == 0:
				if i + 1 != arr_count:
					arr[i + 1] += 1
					arr[i] -= 1
				else:
					extra_0 = 1
					arr[i] -= 1
			else:
				arr[i] -= 1
				extra_0 = 1
			if i != 0:
				temp = arr[i - 1] - 1
				if temp == 0:
					arr[i - 2] += 1
					arr[i - 1] -= 1
				else:
					arr[i - 1] -= 1
					extra_1 = 1
			else:
				extra_1 = 1
			pos = i - 1
			break
	temp = arr_count
	if pos != -1 and arr[pos] == 0:
		temp -= 1
	if pos + 1 != arr_count and arr[pos + 1] == 0:
		temp -= 1
	if extra_0:
		temp += 1
	if extra_1:
		temp += 1
	if extra_0:
		if pos + 1 < arr_count and (pos + 1) % 2 != 0 or (pos + 2 < arr_count and (pos + 2) % 2 != 0):
			temp -= 1
			add = 1
	print(temp)
	if pos == -1:
		if extra_1:
			res += '1 '
		if extra_0 and add == 0:
			res += '1 '
	for i in range(0, pos + 1):
		if arr[pos] != 0 and i == pos:
			res += str(arr[i]) + ' '
		elif i != pos:
			res += str(arr[i]) + ' '
		if i == pos:
			if extra_1:
				res += '1 '
			if extra_0 and add == 0:
				res += '1 '
	for i in range(pos + 1, arr_count):
		if arr[i] != 0 and i % 2 != 0:
			res += str(arr[i] + add) + ' '
			add = 0
	for i in range(pos + 1, arr_count):
		if arr[i] != 0 and i % 2 == 0:
			res += str(arr[i]) + ' '
	print(res)
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(arr):
	last = 0
	if len(arr) % 2 == 0:
		last += arr.pop()
	ones = arr.pop()
	last += ones
	if arr:
		arr[-1] -= 1
		if arr[-1] == 0:
			arr.pop()
			arr[-1] += 1
		else:
			arr.append(1)
	else:
		arr.append(1)
	arr.append(last - ones + 1)
	if ones > 1:
		arr.append(ones - 1)
	print(len(arr))
	print(' '.join(map(str, arr)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(n, arr):
	if n % 2 == 1:
		if n >= 3:
			x = arr.pop()
			y = arr.pop()
			if y - 1 != 0:
				arr.append(y - 1)
				arr.append(1)
				arr.append(1)
				arr.append(x - 1)
			else:
				arr[-1] += 1
				arr.append(1)
				arr.append(x - 1)
		else:
			x = arr.pop()
			arr.append(1)
			arr.append(1)
			arr.append(x - 1)
	elif n >= 4:
		z = arr.pop()
		x = arr.pop()
		arr[-1] -= 1
		if arr[-1] != 0:
			arr.append(1)
			arr.append(z + 1)
			arr.append(x - 1)
		else:
			arr.pop()
			arr[-1] += 1
			arr.append(z + 1)
			arr.append(x - 1)
	else:
		z = arr.pop()
		x = arr.pop()
		arr.append(1)
		arr.append(z + 1)
		arr.append(x - 1)
	while arr[-1] == 0:
		arr.pop()
	print(len(arr))
	print(' '.join(map(str, arr)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr_count, arr)


import os
import sys

def whatsNext(arr):

	def sanitize(arr):
		clean_arr = []
		clean_arr.append(arr[0])
		i = 1
		while i < len(arr) - 1:
			if arr[i] == 0:
				clean_arr[i - 1] += arr[i + 1]
				i += 2
			else:
				clean_arr.append(arr[i])
				i += 1
		if i == len(arr) - 1:
			if arr[i] != 0:
				clean_arr.append(arr[i])
		return clean_arr

	def getNumber(arr):
		new_arr = []
		if len(arr) % 2 == 0:
			new_arr.append(arr[-2] - 1)
			new_arr.insert(0, arr[-1] + 1)
			new_arr.insert(0, 1)
			if len(arr) > 3:
				new_arr.insert(0, arr[-3] - 1)
				return arr[:len(arr) - 3] + new_arr
			else:
				return new_arr
		else:
			new_arr.append(arr[-1] - 1)
			new_arr.insert(0, 1)
			new_arr.insert(0, 1)
		if len(arr) > 1:
			new_arr.insert(0, arr[-2] - 1)
			return arr[:len(arr) - 2] + new_arr
		else:
			return new_arr
	new_compressed_bin = sanitize(getNumber(arr))
	print(len(new_compressed_bin))
	for i in new_compressed_bin:
		print(str(i) + ' ', end='')
	print()
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(arr):
	n = len(arr)
	if n % 2 == 0:
		if n == 2 and arr[0] == 1:
			return [1, arr[1] + 1]
		elif n == 2:
			return [1, arr[1] + 1, arr[0] - 1]
		ans = []
		for i in range(n - 3):
			ans.append(arr[i])
		if arr[n - 3] == 1:
			ans[-1] += 1
			ans.append(arr[n - 1] + 1)
			if arr[n - 2] > 1:
				ans.append(arr[n - 2] - 1)
			return ans
		ans.append(arr[n - 3] - 1)
		ans.append(1)
		ans.append(arr[n - 1] + 1)
		if arr[n - 2] > 1:
			ans.append(arr[n - 2] - 1)
		return ans
	ans = []
	if n == 1:
		ans += [1, 1]
		if arr[0] > 1:
			ans.append(arr[0] - 1)
		return ans
	for i in range(n - 2):
		ans.append(arr[i])
	if arr[n - 2] > 1:
		ans.append(arr[n - 2] - 1)
		ans += [1, 1]
	else:
		ans[-1] += 1
		ans.append(1)
	if arr[n - 1] > 1:
		ans.append(arr[n - 1] - 1)
	return ans
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	res = whatsNext(arr)
	print(len(res))
	for num in res:
		print(num, end=' ')
	print(' ')


import os
import sys

def whatsNext(arr):
	if len(arr) % 2:
		arr.append(0)
	if len(arr) == 2:
		arr = [1, arr[-1] + 1, arr[-2] - 1]
	elif arr[-3] == 1:
		arr = arr[:-4] + [arr[-4] + 1, arr[-1] + 1, arr[-2] - 1]
	else:
		arr = arr[:-3] + [arr[-3] - 1, 1, arr[-1] + 1, arr[-2] - 1]
	while arr[-1] == 0:
		arr.pop()
	return arr
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	arr = whatsNext(arr)
	print(len(arr))
	print(' '.join(map(str, arr)))


def whats_next(number_list):
	number_list = list(number_list)
	length = len(number_list)
	if length == 1:
		number_list.insert(0, 1)
		number_list.insert(0, 1)
		number_list[2] -= 1
		if number_list[-1] == 0:
			number_list.pop()
	elif length == 2:
		if number_list[0] == 1:
			number_list[1] += 1
		else:
			number_list = [1, number_list[1] + 1, number_list[0] - 1]
	elif length % 2 == 0:
		number_list.insert(-2, 1)
		number_list[-4] -= 1
		(number_list[-2], number_list[-1]) = (number_list[-1] + 1, number_list[-2] - 1)
		if number_list[-4] == 0:
			number_list.pop(-4)
			number_list[-4] += number_list[-3]
			number_list.pop(-3)
		if (number_list[-2], number_list[-1]) == (0, 0):
			number_list = number_list[:-2]
		elif number_list[-2] == 0:
			number_list.pop(-2)
			number_list[-2] += number_list[-1]
			number_list.pop(-1)
		elif number_list[-1] == 0:
			number_list.pop(-1)
	elif length % 2 == 1:
		number_list.insert(-1, 1)
		number_list.insert(-1, 1)
		number_list[-4] -= 1
		number_list[-1] -= 1
		if number_list[-4] == 0:
			number_list.pop(-4)
			number_list[-4] += number_list[-3]
			number_list.pop(-3)
		if number_list[-1] == 0:
			number_list.pop()
	print(len(number_list))
	for iii in number_list:
		print(iii, end=' ')
	print()
	return 0
test_cases = int(input())
n_list = []
num_list_list = []
for _ in range(test_cases):
	n = int(input())
	num_list = list(map(int, input().rstrip().split()))
	n_list.append(n)
	num_list_list.append(num_list)
for _ in num_list_list:
	whats_next(_)


import os
import sys

def whats_next(a):
	n = len(a)
	if n == 1:
		ans = [1, 1, a[0] - 1]
	elif n == 2:
		ans = [1, a[1] + 1, a[0] - 1]
	elif n % 2 == 1:
		if a[n - 2] == 1:
			ans = a[0:n - 3] + [a[n - 3] + 1, 1, a[n - 1] - 1]
		else:
			ans = a[0:n - 2] + [a[n - 2] - 1, 1, 1, a[n - 1] - 1]
	elif a[n - 3] == 1:
		ans = a[0:n - 4] + [a[n - 4] + 1, a[n - 1] + 1, a[n - 2] - 1]
	else:
		ans = a[0:n - 3] + [a[n - 3] - 1, 1, a[n - 1] + 1, a[n - 2] - 1]
	if ans[-1] == 0:
		ans = ans[:-1]
	return ans
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	res = whats_next(arr)
	print(len(res))
	print(' '.join(map(str, res)))


for xx in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = []
	if len(l) % 2 == 0:
		if len(l) == 2:
			if l[0] > 1:
				ans.append(1)
				ans.append(l[1] + 1)
				ans.append(l[0] - 1)
			else:
				l[1] += 1
				ans = l
		else:
			for i in l[:-3]:
				ans.append(i)
			if l[-3] - 1 > 0:
				ans.append(l[-3] - 1)
				ans.append(1)
			else:
				ans[-1] += 1
			ans.append(l[-1] + 1)
			ans.append(l[-2] - 1)
	elif len(l) == 1:
		ans.append(1)
		ans.append(1)
		ans.append(l[0] - 1)
	else:
		for i in l[:-2]:
			ans.append(i)
		if l[-2] - 1:
			ans.append(l[-2] - 1)
			ans.append(1)
			ans.append(1)
			if l[-1] - 1:
				ans.append(l[-1] - 1)
		else:
			ans[-1] += 1
			ans.append(1)
			if l[-1] - 1:
				ans.append(l[-1] - 1)
	if 0 in ans:
		ans.remove(0)
	print(len(ans))
	print(*ans)


import os
import sys

def whatsNext(arr):
	groups = [((i + 1) % 2, x) for (i, x) in enumerate(arr)]
	i = len(groups) - 1
	if groups[i][0] == 0:
		i -= 1
	n = groups[i][1]
	n_tail = sum((groups[j][1] for j in range(i, len(groups))))
	del groups[i:]
	if i > 0:
		groups.append((0, -1))
	groups.append((1, 1))
	groups.append((0, 1 + n_tail - n))
	groups.append((1, n - 1))
	result = []
	for i in range(len(groups)):
		if result:
			(code, count) = result[-1]
		else:
			(code, count) = (None, None)
		(next_code, next_count) = groups[i]
		if next_code != code and next_count != 0:
			result.append((next_code, next_count))
		else:
			result.pop()
			count += next_count
			if count != 0:
				result.append((code, count))
	print(len(result))
	print(' '.join((str(group[1]) for group in result)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def count_ones(xs):
	r = sum((xs[i] for i in range(0, len(xs), 2)))
	return r

def compress(xs):
	while True:
		try:
			i = xs.index(0)
			if i == len(xs) - 1:
				xs = xs[:-1]
			else:
				xs[i - 1] += xs[i + 1]
				xs = xs[:i] + xs[i + 2:]
		except ValueError:
			break
	return xs

def whats_next(xs):
	k = count_ones(xs)
	if len(xs) % 2 == 0:
		if len(xs) < 3:
			us = xs[:-2] + [1, xs[-1] + 1, xs[-2] - 1]
		else:
			us = xs[:-3] + [xs[-3] - 1, 1, xs[-1] + 1, xs[-2] - 1]
	elif len(xs) == 1:
		us = [1, 1, xs[0] - 1]
	else:
		us = xs[:-2] + [xs[-2] - 1, 1, 1, xs[-1] - 1]
	us = compress(us)
	assert count_ones(us) == k
	return us

def whatsNext(arr):
	cs = whats_next(arr)
	print('{}\n{}'.format(len(cs), ' '.join((str(x) for x in cs))))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = [int(x) for x in input().split()]
	whatsNext(arr)


def f(a):
	n = len(a)
	w = n - 2 + n % 2
	if w == n - 1:
		a.append(1)
	else:
		a[n - 1] += 1
	if a[w] != 1:
		a.append(a[w] - 1)
	a[w] = 1
	if w:
		a[w - 1] -= 1
		if a[w - 1] == 0:
			a[w - 2] += 1
			a[w] = a.pop()
			a[w - 1] = a.pop()
t = int(input())
for _ in range(t):
	input()
	a = list(map(int, input().split()))
	f(a)
	print(len(a))
	print(*a, sep=' ')


import os
import sys

def whatsNext(arr):
	if len(arr) <= 2:
		z = 0
		if len(arr) == 2:
			z = arr[1]
		if arr[0] > 1:
			print(3)
			print(1, z + 1, arr[0] - 1)
		else:
			print(2)
			print(1, z + 1)
		return
	if len(arr) % 2 == 1:
		(p, m, n, k) = (*arr[-3:], 0)
		result = arr[:-3]
	else:
		(p, m, n, k) = arr[-4:]
		result = arr[:-4]
	if m > 1:
		result += [p, m - 1, 1]
	else:
		result += [p + 1]
	if n > 1:
		result += [k + 1, n - 1]
	else:
		result += [1 + k]
	print(len(result))
	print(' '.join(map(str, result)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(arr):
	n = len(arr)
	if n % 2 == 0:
		if n == 2:
			arr = [1, arr[1] + 1, arr[0] - 1]
		elif arr[-3] == 1:
			arr[-4] += 1
			arr[-3] = 1 + arr[-1]
			arr[-2] -= 1
			arr.pop()
		else:
			arr[-3] -= 1
			a = arr[-2] - 1
			arr[-2] = 1
			arr[-1] += 1
			arr.append(a)
	elif n > 1:
		if arr[-2] == 1:
			arr[-3] += 1
			arr[-1] -= 1
		else:
			arr[-2] -= 1
			a = arr[-1] - 1
			arr[-1] = 1
			arr.append(1)
			arr.append(a)
	else:
		arr = [1, 1, arr[0] - 1]
	if arr[-1] == 0:
		arr.pop()
	print(len(arr))
	print(' '.join(map(str, arr)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(arr):
	if len(arr) % 2 == 1:
		arr.append(0)
	count = arr[-2]
	if len(arr) >= 3:
		arr[-3] -= 1
	arr[-2] = 1
	arr[-1] += 1
	arr.append(count - 1)
	answer = []
	for i in range(len(arr)):
		answer.append(arr[i])
		if len(answer) >= 3 and answer[-2] == 0:
			answer[-3] += answer[-1]
			answer.pop()
			answer.pop()
	if answer[-1] == 0:
		answer.pop()
	print(len(answer))
	print(' '.join(map(str, answer)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(arr):
	n = len(arr)
	if n % 2 == 0:
		if n == 2:
			if arr[0] > 1:
				return [1, arr[-1] + 1, arr[0] - 1]
			else:
				return [1, arr[-1] + 1]
		elif arr[-3] > 1:
			if arr[-2] > 1:
				return arr[:-3] + [arr[-3] - 1, 1, arr[-1] + 1, arr[-2] - 1]
			else:
				return arr[:-3] + [arr[-3] - 1, 1, arr[-1] + 1]
		elif arr[-2] > 1:
			return arr[:-4] + [arr[-4] + 1, arr[-1] + 1, arr[-2] - 1]
		else:
			return arr[:-4] + [arr[-4] + 1, arr[-1] + 1]
	elif n == 1:
		if arr[0] > 1:
			return [1, 1, arr[0] - 1]
		else:
			return [1, 1]
	elif arr[-2] > 1:
		if arr[-1] > 1:
			return arr[:-2] + [arr[-2] - 1, 1, 1, arr[-1] - 1]
		else:
			return arr[:-2] + [arr[-2] - 1, 1, 1]
	elif arr[-1] > 1:
		return arr[:-3] + [arr[-3] + 1, 1, arr[-1] - 1]
	else:
		return arr[:-3] + [arr[-3] + 1, 1]
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	L = whatsNext(arr)
	print(str(len(L)))
	print(' '.join(map(str, L)))


from itertools import cycle
for test in range(int(input())):
	size = int(input())
	ar = [int(a) * b for (a, b) in zip(('1 ' + input()).split(), cycle((-1, 1)))]
	if size % 2:
		ar = ar[:-2] + [ar[-2] + 1, 1, -1, ar[-1] - 1]
	else:
		ar = ar[:-3] + [ar[-3] + 1, 1, -1, ar[-1], ar[-2] - 1]
	dig = 2
	while ar[0] <= 0:
		del ar[0]
	result = []
	sign = None
	for n in ar:
		if n:
			if sign == (n < 0):
				result[-1] += abs(n)
			else:
				sign = n < 0
				result.append(abs(n))
	print(len(result))
	print(*result)


import os
import sys

def normalize(rle):
	rle = [(d, l) for (d, l) in rle if l != 0]
	new_rle = [rle[0]]
	for (d, l) in rle[1:]:
		if d == new_rle[-1][0]:
			new_rle[-1] = (new_rle[-1][0], new_rle[-1][1] + l)
		else:
			new_rle.append((d, l))
	return new_rle

def do0(rle):
	assert len(rle) > 1
	if len(rle) == 2:
		new_rle = [(1, 1), (0, rle[-1][1] + 1), (1, rle[-2][1] - 1)]
	else:
		new_end = [(0, rle[-3][1] - 1), (1, 1), (0, rle[-1][1] + 1), (1, rle[-2][1] - 1)]
		new_rle = rle[:-3] + new_end
	return normalize(new_rle)

def do1(rle):
	if len(rle) == 1:
		new_rle = [(1, 1), (0, 1), (1, rle[0][1] - 1)]
	else:
		new_end = [(0, rle[-2][1] - 1), (1, 1), (0, 1), (1, rle[-1][1] - 1)]
		new_rle = rle[:-2] + new_end
	return normalize(new_rle)

def whatsNext(arr):
	rle = list(zip([1, 0] * len(arr), arr))
	if rle[-1][0] == 0:
		ans = do0(rle)
	else:
		ans = do1(rle)
	print(len(ans))
	print(' '.join(map(lambda x: str(x[1]), ans)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


def solve(n, arr):
	n1 = arr[n - 1]
	if (n - 1) % 2 == 0:
		if n - 2 < 0:
			arr = [1, 1, n1 - 1]
		else:
			n2 = arr[n - 2]
			del arr[n - 1]
			del arr[n - 2]
			arr += [n2 - 1, 1, 1, n1 - 1]
	else:
		n2 = arr[n - 2]
		if n - 3 < 0:
			del arr[n - 1]
			del arr[n - 2]
			if n2 == 1:
				arr = [n2, n1 + 1]
			else:
				arr = [1, n1 + 1, n2 - 1]
		else:
			n3 = arr[n - 3]
			del arr[n - 1]
			del arr[n - 2]
			del arr[n - 3]
			arr += [n3 - 1, 1, n1 + 1, n2 - 1]
	idx = 0
	n = len(arr)
	while True:
		if idx == n:
			break
		if arr[idx] == 0:
			if idx == n - 1:
				del arr[idx]
				break
			else:
				arr[idx - 1] += arr[idx + 1]
				del arr[idx + 1]
				del arr[idx]
				n -= 2
		else:
			idx += 1
	return arr
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	res = solve(n, arr)
	print(len(res))
	print(*res)


import os
import sys

def whatsNext(arr):
	res = whats_next(arr)
	print(len(res))
	print(' '.join(map(str, res)))

def whats_next(arr):
	return compress(trailing_zeros(arr) if even_len(arr) else trailing_ones(arr))

def compress(arr):
	while arr[0] == 0:
		del arr[0]
	while arr[-1] == 0:
		del arr[-1]
	while 0 in arr:
		index = arr.index(0)
		arr[index - 1:index + 2] = [arr[index - 1] + arr[index + 1]]
	return arr

def trailing_zeros(arr):
	arr[-2:] = (1, arr[-1] + 1, arr[-2] - 1)
	try:
		arr[-4] -= 1
	except IndexError:
		pass
	return arr

def trailing_ones(arr):
	arr[:0] = [0]
	(zeros, ones) = arr[-2:]
	arr[-1] -= 1
	arr[-2] -= 1
	arr[-1:-1] = [1, 1]
	if zeros == 1:
		arr[-5:-2] = [sum(arr[-5:-2])]
	return [item for item in arr if item >= 0]

def even_len(arr):
	return not bool(len(arr) % 2)
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


def whatsNext(arr):
	parts = [('0' if i % 2 else '1') * length for (i, length) in enumerate(arr)]
	printBinArrRes(nextbin(list(''.join(parts))))

def printBinArrRes(bin_i):
	bin_i = ''.join(bin_i).lstrip('0')
	one_group = [len(x) for x in bin_i.split('0') if x]
	zero_group = [len(x) for x in bin_i.split('1') if x]
	assert len(zero_group) <= len(one_group)
	res = []
	for (i, j) in enumerate(zero_group):
		res.append(one_group[i])
		res.append(j)
	if len(one_group) > len(zero_group):
		res.append(one_group[-1])
	print(len(res))
	print(' '.join((str(x) for x in res)))

def nextbin(binarr):
	res = binarr[:]
	res.insert(0, '0')
	for i in range(len(res) - 1, -1, -1):
		if res[i] == '0':
			continue
		if res[i - 1] == '1':
			continue
		res[i - 1:i + 1] = ['1', '0']
		res[i + 1:] = list(sorted(res[i + 1:]))
		return res
	raise RuntimeError(res)

def setcount(number):
	return list(bin(number)).count('1')

def printres(chunks):
	if chunks[-1] == 0:
		del chunks[-1]
	print(len(chunks))
	print(' '.join((str(x) for x in chunks)))

def whatsNext(chunks):
	res = chunks[:]
	one_chunks = [j for (i, j) in enumerate(chunks) if i % 2 == 0]
	zero_chunks = [j for (i, j) in enumerate(chunks) if i % 2 == 1]
	last_i = len(chunks) - 1
	last_one_i = last_i - last_i % 2
	if len(chunks) == 1:
		chunks.append(0)
	if len(chunks) == 2:
		return printres([1, chunks[1] + 1, chunks[0] - 1])
	remaining_ones = res[last_one_i] - 1
	res[last_one_i - 1] -= 1
	res[last_one_i] = 1
	if last_i != last_one_i:
		res[last_one_i + 1] += 1
	else:
		res.append(1)
	res.append(remaining_ones)
	if not res[last_one_i - 1]:
		res[last_one_i - 2:last_one_i + 1] = [res[last_one_i - 2] + 1]
	return printres(res)
	for i in range(len(res) - 1, -1, -1):
		if res[i] == '0':
			continue
		if res[i - 1] == '1':
			continue
		res[i - 1:i + 1] = ['1', '0']
		res[i + 1:] = list(sorted(res[i + 1:]))
		return res
	raise RuntimeError(res)

def whatsNext2(arr):
	parts = [('0' if i % 2 else '1') * length for (i, length) in enumerate(arr)]
	printBinArrRes(nextbin(list(''.join(parts))))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(arr):
	len_arr = len(arr)
	if len_arr == 1:
		D = [1, 1]
		if arr[0] > 1:
			D.append(arr[0] - 1)
	elif len_arr % 2 == 1:
		D = arr[:-2]
		if arr[-2] > 1:
			D.append(arr[-2] - 1)
			D.append(1)
		else:
			D[-1] += 1
		D.append(1)
		if arr[-1] > 1:
			D.append(arr[-1] - 1)
	elif len_arr == 2:
		D = [1, arr[-1] + 1]
		if arr[-2] > 1:
			D.append(arr[-2] - 1)
	else:
		D = arr[:-3]
		if arr[-3] > 1:
			D.append(arr[-3] - 1)
			D.append(1)
		else:
			D[-1] += 1
		D.append(arr[-1] + 1)
		if arr[-2] > 1:
			D.append(arr[-2] - 1)
	print(len(D))
	for el in D:
		print(el, end=' ')
	print()
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whats_next(arr):
	if len(arr) % 2 == 1:
		arr.append(0)
	arr = [0, 0] + arr
	(z1, i2, z2) = arr[-3:]
	arr = arr[:-3] + [z1 - 1, 1, 1 + z2, i2 - 1]
	return clean_array(arr)

def clean_array(arr):
	if arr[0] == 0:
		arr = arr[2:]
	if arr[-1] == 0:
		arr = arr[:-1]
	i = 0
	while i < len(arr) // 2:
		if arr[2 * i + 1] <= 0:
			arr = arr[:2 * i] + [arr[2 * i] + arr[2 * i + 2]] + arr[2 * i + 3:]
		i += 1
	return arr

def whatsNext(arr):
	res = whats_next(arr)
	print(len(res))
	print(' '.join(map(str, res)))
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

def whatsNext(arr):
	if len(arr) % 2 != 0:
		if len(arr) < 3:
			arr[-1] -= 1
			arr.insert(-1, 1)
			arr.insert(-2, 1)
		else:
			arr[-1] -= 1
			arr.insert(-1, 1)
			arr.insert(-2, 1)
			arr[-4] -= 1
	elif len(arr) < 3 and arr[0] == 1:
		arr[-2] -= 1
		arr.insert(-2, 1)
		arr.insert(-3, 1)
	elif len(arr) < 3 and arr[0] != 1:
		i = arr[0] - 1
		arr.append(i)
		arr[1] += 1
		arr[0] = 1
	else:
		arr[-2] -= 1
		arr.insert(-2, arr[-1] + 1)
		arr.insert(-3, 1)
		arr[-5] -= 1
		arr.pop()
	while 0 in arr:
		ind = arr.index(0)
		try:
			arr[ind - 1] = arr[ind - 1] + arr[ind + 1]
			del arr[ind]
			del arr[ind]
		except:
			del arr[ind]
	print(len(arr))
	print(*arr)
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	whatsNext(arr)


import os
import sys

class Solution(object):

	def one(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, 1])
		else:
			return (3, [1, 1, nums[0] - 1])

	def two(self, nums):
		if nums[0] - 1 == 0:
			return (2, [1, nums[1] + 1])
		else:
			return (3, [1, nums[1] + 1, nums[0] - 1])

	def odd(self, num, nums):
		if nums[-1] - 1 == 0:
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] -= 1
			nums.insert(-1, 1)
			if nums[-3] - 1 == 0:
				del nums[-3]
				nums[-3] += 1
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def even(self, num, nums):
		if nums[-2] - 1 == 0:
			del nums[-2]
			nums[-1] += 1
			if nums[-2] - 1 == 0:
				del nums[-2]
				nums[-2] += 1
			else:
				nums.insert(-1, 1)
				nums[-3] -= 1
		else:
			nums[-1] += 1
			nums.append(nums[-2] - 1)
			del nums[-3]
			if nums[-3] - 1 == 0:
				nums[-4] += 1
				del nums[-3]
			else:
				nums[-3] -= 1
				nums.insert(-2, 1)
		return (len(nums), nums)

	def solve(self, num, nums):
		if num == 1:
			return self.one(nums)
		if num == 2:
			return self.two(nums)
		if num % 2 == 1:
			return self.odd(num, nums)
		else:
			return self.even(num, nums)
solution = Solution()
total = int(input(''))
result1 = 0
result2 = []
for index in range(total):
	num = int(input(''))
	numsString = input('')
	nums = list(map(int, str.split(numsString)))
	(result1, result2) = solution.solve(num, nums)
	print(result1)
	print(' '.join((str(x) for x in result2)))