Ashish has a binary string $s$ of length $n$ that he wants to sort in non-decreasing order.

He can perform the following operation:

Choose a subsequence of any length such that its elements are in non-increasing order. Formally, choose any $k$ such that $1 \leq k \leq n$ and any sequence of $k$ indices $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$ such that $s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}$.

Reverse this subsequence in-place. Formally, swap $s_{i_1}$ with $s_{i_k}$, swap $s_{i_2}$ with $s_{i_{k-1}}$, $\ldots$ and swap $s_{i_{\lfloor k/2 \rfloor}}$ with $s_{i_{\lceil k/2 \rceil + 1}}$ (Here $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$, and $\lceil x \rceil$ denotes the smallest integer not less than $x$)

Find the minimum number of operations required to sort the string in non-decreasing order. It can be proven that it is always possible to sort the given binary string in at most $n$ operations.


-----Input-----

The first line contains a single integer $t$ $(1 \le t \le 1000)$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ $(1 \le n \le 1000)$  — the length of the binary string $s$.

The second line of each test case contains a binary string $s$ of length $n$ containing only $0$s and $1$s.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.


-----Output-----

For each test case output the following:

The minimum number of operations $m$ in the first line ($0 \le m \le n$).

Each of the following $m$ lines should be of the form: $k$ $i_1$ $i_2$ ... $i_{k}$, where $k$ is the length and $i_1 \lt i_2 \lt ... \lt i_{k}$ are the indices of the chosen subsequence. For them the conditions from the statement must hold.


-----Examples-----

Input
3
7
0011111
5
10100
6
001000
Output
0
1
4 1 3 4 5 
1
3 3 5 6


-----Note-----

In the first test case, the binary string is already sorted in non-decreasing order.

In the second test case, we can perform the following operation:

$k = 4:$ choose the indices $\{1, 3, 4, 5\}$

$\underline{1}$ $0$ $\underline{1}$ $\underline{0}$ $\underline{0}$ $\rightarrow $ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$ $\underline{1}$

In the third test case, we can perform the following operation:

$k = 3:$ choose the indices $\{3, 5, 6\}$

$0$ $0$ $\underline{1}$ $0$ $\underline{0}$ $\underline{0}$ $\rightarrow $ $0$ $0$ $\underline{0}$ $0$ $\underline{0}$ $\underline{1}$

Source: codeforces | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l = 0
	r = n - 1
	left = []
	right = []
	while l < r:
		while l < n and s[l] != '1':
			l += 1
		while r >= 0 and s[r] != '0':
			r -= 1
		if l >= r:
			break
		left.append(l + 1)
		right.append(r + 1)
		l += 1
		r -= 1
	l = len(left)
	r = len(right)
	right = right[::-1]
	if l + r == 0:
		print('0')
	else:
		print('1')
		print(l + r, end=' ')
		for e in left:
			print(e, end=' ')
		for e in right:
			print(e, end=' ')
		print()


def fun(ans):
	o = []
	z = []
	i = 0
	j = len(ans) - 1
	while i < j:
		if ans[i] != '1':
			i += 1
		if ans[j] != '0':
			j -= 1
		if i < j and ans[j] == '0' and (ans[i] == '1'):
			o.append(i + 1)
			z.append(j + 1)
			i += 1
			j -= 1
	x = o + z[::-1]
	return x
for _ in range(int(input())):
	x = input()
	arr = input()
	x = fun(arr)
	if not x:
		print(0)
	else:
		print(1)
		print(len(x), end=' ')
		for i in x:
			print(i, end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	v = 0
	op = []
	c = s.count('1')
	for i in range(n):
		if s[i] == '0' and i > n - 1 - c:
			op.append(i + 1)
			v += 1
		elif s[i] == '1' and i <= n - 1 - c:
			op.append(i + 1)
			v += 1
	if v == 0:
		print(0)
	else:
		print(1)
		print(v, end=' ')
		for i in op:
			print(i, end=' ')
		print()


import sys
inp = sys.stdin.readline

def solve():
	n = int(input())
	a = list(input().strip())
	r = []
	while True:
		i = 0
		j = len(a) - 1
		f = []
		b = []
		while True:
			while i < len(a):
				if a[i] == '1':
					break
				i += 1
			while j >= 0:
				if a[j] == '0':
					break
				j -= 1
			if i < j:
				f.append(i + 1)
				b.append(j + 1)
				(a[i], a[j]) = (a[j], a[i])
				z = 1
			else:
				break
		if len(f):
			b.reverse()
			r.append(f + b)
		else:
			break
	print(len(r))
	for i in r:
		print(len(i), end=' ')
		print(' '.join(map(str, i)))

def main():
	for i in range(int(inp())):
		solve()
main()


for _ in range(int(input())):
	input()
	s = [int(x) for x in input()]
	x = [0, 0]
	for i in s:
		x[i] += 1
	y = []
	for (i, j) in enumerate(s):
		if j == 1 and i < x[0]:
			y.append(i + 1)
		elif j == 0 and i >= x[0]:
			y.append(i + 1)
	print(1 if y else 0)
	if y:
		print(len(y), *y)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = 0
	for i in range(n):
		if s[i] == '0':
			a += 1
	ans = []
	for i in range(n):
		if i < a and s[i] == '1':
			ans += [i + 1]
		elif i >= a and s[i] == '0':
			ans += [i + 1]
	if len(ans) == 0:
		print(0)
	elif len(ans) > 0:
		print(1)
		print(len(ans), end=' ')
		for i in ans:
			print(i, end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = sorted(s)
	a = ''.join(a)
	if s == a:
		print(0)
	else:
		count = 0
		l = []
		for i in range(n):
			if a[i] == s[i]:
				pass
			else:
				count += 1
				l.append(i + 1)
		l = sorted(l)
		print(1)
		print(count, *l)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	f0 = []
	f1 = []
	for (i, x) in enumerate(s):
		if x == '0':
			f0.append(i + 1)
		else:
			f1.append(i + 1)
	f0.reverse()
	if not f0 or not f1 or f0[0] < f1[0]:
		print(0)
		continue
	print(1)
	res = []
	for i in range(min(len(f1), len(f0))):
		if f1[i] < f0[i]:
			res.append(f0[i])
			res.append(f1[i])
	print(len(res), end=' ')
	res.sort()
	for x in res:
		print(x, end=' ')
	print()


T = int(input())
while T:
	T -= 1
	n = int(input())
	s = input()
	on = 0
	zr = 0
	for i in s:
		if i == '1':
			on += 1
		else:
			zr += 1
	if ''.join(sorted(s)) == s:
		print(0)
		continue
	print(1)
	a = []
	for i in range(len(s)):
		if i < zr and s[i] == '1':
			a.append(i)
		elif s[i] == '0' and i >= zr:
			a.append(i)
	print(len(a), end=' ')
	for i in a:
		print(i + 1, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	string = input()
	zero = string.count('0')
	one = string.count('1')
	(notcorz, notcorro) = ([], [])
	for j in range(zero, n):
		if string[j] == '0':
			notcorro.append(j)
	for j in range(zero):
		if string[j] == '1':
			notcorz.append(j)
	if len(notcorz) + len(notcorro) == 0:
		print(0)
		continue
	else:
		print(1)
		print(len(notcorro) + len(notcorz), end=' ')
		for el in notcorz:
			print(el + 1, end=' ')
		for el in notcorro:
			print(el + 1, end=' ')
		print()


for ii in range(int(input())):
	n = int(input())
	s = list(input())
	(a, o, z, co, cz, cou) = ([], [], [], 0, 0, 0)
	for jj in range(n):
		if s[jj] == '0':
			cz += 1
			z.append(jj)
		else:
			co += 1
			o.append(jj)
	for jj in o:
		if jj < cz:
			a.append(jj + 1)
		else:
			break
	for jj in z:
		if jj >= cz:
			a.append(jj + 1)
	if a:
		print(1)
		print(len(a), *a)
	else:
		print(0)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	s = input()
	q = sorted(s)
	res = []
	for i in range(n):
		if s[i] != q[i]:
			res.append(i)
	if len(res) == 0:
		print(0)
	else:
		print(1)
		ans = []
		for i in res:
			ans.append(i + 1)
		print(len(res), *ans)


ret = []
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	how1 = s.count('1')
	f = []
	ans = '0' * (n - how1) + '1' * how1
	for i in range(n):
		if s[i] != ans[i]:
			f.append(i + 1)
	if f:
		g = [1, len(f)]
		g.extend(f)
		ret.append(g)
	else:
		ret.append([0])
for i in range(t):
	if ret[i][0] == 1:
		print(1)
		print(*ret[i][1:])
	else:
		print(0)


def dosth(n, st):
	arr = []
	ids = sorted(st)
	for (x, (i, j)) in enumerate(zip(st, ids)):
		if i != j:
			arr.append(x + 1)
	if not arr:
		print(0)
		return
	print(1)
	print(len(arr), *arr)
t = eval(input())
for _ in range(t):
	n = eval(input())
	st = input()
	dosth(n, st)


def solve(n, s):
	left = 0
	right = n - 1
	ans1 = []
	ans2 = []
	while left < n and right >= 0:
		while s[left] != '1':
			left += 1
			if left == n:
				return (ans1, ans2)
		while s[right] != '0':
			right -= 1
			if right == -1:
				return (ans1, ans2)
		if left < right:
			ans1.append(left + 1)
			ans2.insert(0, right + 1)
			left += 1
			right -= 1
		else:
			return (ans1, ans2)
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	(out, outt) = solve(n, s)
	out.extend(outt)
	if len(out) == 0:
		print(0)
	else:
		print(1)
		print(len(out), end=' ')
		for ele in out:
			print(ele, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = list(s)
	l = sorted(l)
	(a1, a2) = ([], [])
	for i in range(n):
		if s[i] != l[i] and s[i] == '1':
			a1.append(i + 2 - 1)
	for i in range(n - 1, -1, -1):
		if s[i] != l[i] and l[i] == '1':
			a2 = [i + 1] + a2
	if not (a1 != [] or a2 != []):
		print(0)
	else:
		print(1)
		print(len(a1 + a2), *a1, *a2)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	zero = s.count('0')
	ans = []
	for i in range(zero):
		if s[i] == '1':
			ans.append(i + 1)
	for i in range(zero, n):
		if s[i] == '0':
			ans.append(i + 1)
	if ans:
		print(1)
		print(len(ans), *ans)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = ''.join(sorted(s))
	if a == s:
		print(0)
	else:
		ans = []
		for i in range(n):
			if a[i] != s[i]:
				ans.append(i + 1)
		print(1)
		print(len(ans), *ans)


def isSorted(s):
	if s == s.sort():
		return True
	else:
		return False

def solve(s):
	s = [int(x) for x in list(s)]
	if s == sorted(s):
		return (0, 0)
	arr = []
	j = len(s) - 1
	for i in range(len(s)):
		if s[i] == 0:
			continue
		else:
			while j > i:
				if s[j] == 1:
					j -= 1
					continue
				else:
					arr.append(i + 1)
					arr.append(j + 1)
					j -= 1
					break
	arr.sort()
	return (1, [len(arr)] + arr)
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	(val, arr) = solve(s)
	if val == 0:
		print(0)
	else:
		print(val)
		print(*arr)


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	s = input()
	i = 0
	j = n - 1
	while i < n and s[i] == '0':
		i += 1
	while j >= 0 and s[j] == '1':
		j -= 1
	a = []
	b = []
	while i < j and i < n and (j >= 0):
		a.append(i)
		b.append(j)
		i += 1
		j -= 1
		while i < n and s[i] == '0':
			i += 1
		while j >= 0 and s[j] == '1':
			j -= 1
	b.reverse()
	ans = a + b
	if len(ans) == 0:
		t -= 1
		print('0')
		continue
	print(1)
	print(len(ans), end=' ')
	if len(ans) > 0:
		print(' '.join([str(a + 1) for a in ans]))
	t -= 1


test = int(input())
for _ in range(test):
	n = int(input())
	s = input()
	pos = []
	(start, end) = (0, n - 1)
	while start < end:
		while start < end and s[start] != '1':
			start += 1
		while start < end and s[end] != '0':
			end -= 1
		if start < end:
			pos.append(start + 1)
			pos.append(end + 1)
			start += 1
			end -= 1
	if pos:
		pos.sort()
		print(1)
		print(len(pos), end=' ')
		for p in pos:
			print(p, end=' ')
		print()
	else:
		print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	one = s.count('1')
	zero = s.count('0')
	arr = []
	c = 0
	flag = 0
	for i in range(n):
		if i <= zero - 1:
			if s[i] == '1':
				arr.append(i)
				flag = 1
		elif i > zero - 1:
			if s[i] == '0':
				arr.append(i)
				flag = 1
	if flag == 0:
		print(0)
		continue
	for i in range(len(arr) // 2):
		(s[arr[i]], s[arr[len(arr) - 1 - i]]) = (s[arr[len(arr) - 1 - i]], s[arr[i]])
	print(1)
	print(len(arr), end=' ')
	for i in range(len(arr)):
		print(arr[i] + 1, end=' ')
	print()


for _ in range(int(input())):
	n = int(int(input()))
	lis = input()
	c = 0
	s1 = ''
	s = ''
	x = n - 1
	y = 0
	while x >= 0 or y <= x:
		if lis[x] == '1':
			pass
		else:
			for y1 in range(y, x):
				if lis[y1] == '0':
					pass
				else:
					c += 1
					s1 += ' ' + str(y1 + 1)
					s = str(x + 1) + ' ' + s
					y = y1 + 1
					break
		x -= 1
	if c:
		print(1)
		print(str(c * 2) + s1 + ' ' + s)
	else:
		print(c)


t = int(input())
for case in range(t):
	n = int(input())
	s = list(input())
	swap = []
	k = 0
	for i in range(n):
		if s[i] == '1':
			k += 1
	for i in range(n):
		if i < n - k and s[i] == '1':
			swap.append(i + 1)
		elif i >= n - k and s[i] == '0':
			swap.append(i + 1)
	swap_str = str(len(swap)) + ' '
	for i in range(len(swap)):
		swap_str = swap_str + str(swap[i]) + ' '
	if len(swap) != 0:
		print('1')
		print(swap_str[:-1])
	else:
		print('0')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	one = s.count('1')
	if not one:
		print(0)
	else:
		pos = list()
		for i in range(n - one):
			if s[i] == '1':
				pos.append(str(i + 1))
		if pos == []:
			print(0)
		else:
			posz = list()
			for i in range(n - one, n):
				if s[i] == '0':
					posz.append(str(i + 1))
			print(1)
			print(len(pos) + len(posz), ' '.join(pos), ' '.join(posz))


import sys
T = int(sys.stdin.readline())
for r in range(T):
	t = sys.stdin.readline()
	a = list(sys.stdin.readline().rstrip())
	b = sorted(a)
	count = 0
	result = []
	for i in range(len(a)):
		if a[i] != b[i]:
			result.append(i + 1)
			count += 1
	if count == 0:
		print('0')
	else:
		print('1')
		print(count, end=' ')
		for i in result:
			print(i, end=' ')
		print('')


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	ans = 0
	al = []
	x = []
	while a != list(sorted(a)):
		i = 0
		j = n - 1
		while i < j:
			if a[i] == '0':
				i += 1
			if a[j] == '1':
				j -= 1
			if a[i] != '0' and a[j] != '1' and (i < j):
				(a[i], a[j]) = (a[j], a[i])
				x.append(i + 1)
				x.append(j + 1)
				i += 1
				j -= 1
		al.append([len(x)] + list(sorted(x)))
		x = []
	print(len(al))
	for i in al:
		print(*i)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	v = ''.join(sorted(list(s)))
	a = []
	for i in range(n):
		if s[i] != v[i]:
			a.append(i + 1)
	if a:
		print(1)
	print(len(a), *a)


for _ in range(int(input())):
	n = int(input())
	s = input()
	k = n
	ans = []
	i = 0
	j = n - 1
	while i < j:
		while i < j and s[i] != '1':
			i += 1
		while i < j and s[j] != '0':
			j -= 1
		if s[i] == '1' and s[j] == '0':
			ans += [i + 1] + [j + 1]
		i += 1
		j -= 1
	if len(ans) == 0:
		print(0)
		continue
	ans.sort()
	print(1)
	ans = [len(ans)] + ans
	print(*ans)


import sys
import bisect
import math
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 9

def solve():
	n = int(input())
	s = input()
	if '10' not in s:
		print(0)
	else:
		print(1)
		zeros = [i for i in range(n) if s[i] == '0']
		end = len(zeros) - 1
		a = []
		for i in range(n):
			if end < 0 or i > zeros[end]:
				break
			if s[i] == '1':
				a.extend([i, zeros[end]])
				end -= 1
		a.sort()
		print(str(len(a)) + ' ' + ' '.join((str(x + 1) for x in a)))
t = 1
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for m in range(t):
	n = int(input())
	s = list(input())
	i = 0
	k = 0
	j = n - 1
	a = []
	while i < j:
		while i <= j and s[j] == '1':
			j -= 1
		while i <= j and s[i] == '0':
			i += 1
		if i <= j:
			a = a[:k] + [i + 1] + [j + 1] + a[k:]
			k += 1
			j -= 1
			i += 1
	if k:
		print(1)
		print(k * 2, *a)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	aa = sorted(a)
	if a == aa:
		print(0)
	else:
		s = []
		for i in range(n):
			if a[i] != aa[i]:
				s.append(i + 1)
		print(1)
		print(len(s), *s)


def solve():
	for test in range(int(input())):
		n = int(input())
		s = input()
		n0 = s.count('0')
		ans = []
		for i in range(n0):
			if s[i] == '1':
				ans.append(i + 1)
		for i in range(n0, n):
			if s[i] == '0':
				ans.append(i + 1)
		if len(ans) > 0:
			print(1)
			print(len(ans), end=' ')
			print(' '.join((str(x) for x in ans)))
		else:
			print(0)
solve()


for _ in range(int(input())):
	n = int(input())
	arr = input()
	zero = arr.count('0')
	ans = []
	for i in range(zero):
		if arr[i] == '1':
			ans.append(i + 1)
	for i in range(n - 1, zero - 1, -1):
		if arr[i] == '0':
			ans.append(i + 1)
	if not ans:
		print(0)
		continue
	print(1)
	print(len(ans), end=' ')
	print(*sorted(ans))


t = int(input())
for anh in range(t):
	n = int(input())
	s = list(input())
	ss = sorted(s)
	if s == ss:
		print(0)
	else:
		print(1)
		l = []
		for i in range(n):
			if s[i] != ss[i]:
				l.append(str(i + 1))
		print(len(l), end=' ')
		print(' '.join(l))


def solve():
	n = int(input())
	s = input()
	ones = []
	prefix_sum = [0] * n
	if s[0] == '1':
		prefix_sum[0] = 1
	for i in range(n):
		if s[i] == '1':
			ones.append(i)
			prefix_sum[i] = prefix_sum[i - 1] + 1
		else:
			prefix_sum[i] = prefix_sum[i - 1]
	sub = 0
	result = []
	for i in reversed(range(n)):
		if s[i] == '0' and prefix_sum[i] - sub > 0:
			result.append(ones[sub])
			result.append(i)
			sub += 1
	result.sort()
	if len(result) == 0:
		print(0)
		return
	print(1)
	print(len(result), end=' ')
	for i in result:
		print(i + 1, end=' ')
	print()

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


for tt in range(int(input())):
	n = int(input())
	s = input()
	l = [int(x) for x in list(s)]
	ll = l + []
	ll.sort()
	m = 0
	ansm = ''
	if l == ll:
		print(0)
		continue
	c0 = l.count(0)
	c1 = l.count(1)
	ixx = []
	for i in range(n - c1):
		if l[i] == 1:
			ixx.append(str(i + 1))
	for i in range(n - c1, n):
		if l[i] == 0:
			ixx.append(str(i + 1))
	print(1)
	print(f"{len(ixx)} {' '.join(ixx)}")


for _ in range(int(input())):
	safd = input()
	s = list(input())
	ans = []
	while s != sorted(s):
		l = []
		i = 0
		j = len(s) - 1
		while i < j:
			while i < len(s) and s[i] != '1':
				i += 1
			while j >= 0 and s[j] != '0':
				j -= 1
			if i < len(s) and s[i] == '1' and (j >= 0) and (s[j] == '0') and (i < j):
				l.append(i)
				l.append(j)
			i += 1
			j -= 1
		l = sorted(l)
		ans.append(l)
		zeros = 0
		ones = 0
		for k in l:
			if s[k] == '0':
				zeros += 1
			else:
				ones += 1
		for k in l:
			if zeros > 0:
				s[k] = '0'
				zeros -= 1
			else:
				s[k] = '1'
				ones -= 1
	print(len(ans))
	for g in ans:
		print(len(g), end=' ')
		for t in g:
			print(t + 1, end=' ')
		print()


q = int(input())
for tc in range(q):
	n = int(input())
	s = input()
	t = ''.join(sorted(s))
	ans = []
	for i in range(len(s)):
		if s[i] != t[i]:
			ans.append(i)
	val = 1 if len(ans) > 0 else 0
	print(val)
	if val > 0:
		print(len(ans), end=' ')
	for elem in range(len(ans)):
		print(ans[elem] + 1, end=' ')
	print()


n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	ones = []
	for j in range(m):
		if s[j] == '1':
			ones.append(j)
	zeros = []
	for j in range(len(ones)):
		if s[m - 1 - j] == '0':
			zeros.append(m - 1 - j)
		else:
			ones.remove(m - 1 - j)
	l = ones + zeros
	if len(l):
		print(1)
		print(len(l), end=' ')
		l.sort()
		for i in range(len(l)):
			print(l[i] + 1, end=' ')
		print()
	else:
		print(0)


def main():
	for t in range(int(input())):
		n = int(input())
		string = list(input())
		ones = string.count('1')
		zeros = string.count('0')
		ans = []
		for (i, j) in enumerate(string):
			if i < zeros:
				if j == '1':
					ans.append(i + 1)
			elif j == '0':
				ans.append(i + 1)
		if ans:
			print(1)
			print(len(ans), end=' ')
			print(*ans, sep=' ')
		else:
			print(0)
main()


tst = int(input())
for i in range(tst):
	n = int(input())
	s = input()
	srt = ''.join(sorted(list(s)))
	ans = []
	if srt == s:
		print(0)
	else:
		print(1)
		for i in range(len(s)):
			if srt[i] != s[i]:
				ans.append(i + 1)
		print(len(ans), end=' ')
		print(*ans)


import sys, os, io
import math
import bisect
t = int(input())
for a0 in range(t):
	n = int(input())
	s = input()
	z = 0
	for i in s:
		if i == '0':
			z += 1
	res = []
	for i in range(n):
		if i < z and s[i] == '1':
			res.append(i + 1)
		if i >= z and s[i] == '0':
			res.append(i + 1)
	if len(res) == 0:
		print(0)
	else:
		print(1)
		res.insert(0, len(res))
		print(*res)


def revSort(string):
	ans = []
	n = len(string)
	l = []
	for x in string:
		l.append(int(x))
	m = sorted(l)
	if l == m:
		return 0
	else:
		for x in range(n):
			if l[x] != m[x]:
				ans.append(x + 1)
	return [len(ans)] + ans
t = int(input())
final = []
for _ in range(t):
	n = int(input())
	string = input()
	a = revSort(string)
	if a == 0:
		final.append(0)
	else:
		final.append(1)
		final.append(a)
for _ in range(len(final)):
	p = final[_]
	if type(p) == list:
		for x in p:
			print(x, end=' ')
		print()
	else:
		print(p)


for _ in range(int(input())):
	n = int(input())
	str_ = input()
	ind = []
	cnt = str_.count('0')
	for i in range(cnt):
		if str_[i] == '1':
			ind.append(i + 1)
	for i in range(cnt, n):
		if str_[i] == '0':
			ind.append(i + 1)
	if len(ind) == 0:
		print(0)
	else:
		print(1)
		print(len(ind), *ind)


t = int(input())
for q in range(t):
	n = int(input())
	s = input()
	z = s.count('0')
	o = s.count('1')
	arr = [i for i in s]
	lis = sorted(s)
	ans = []
	for i in range(z):
		if s[i] == '1':
			ans.append(i + 1)
	for i in range(z, n):
		if s[i] == '0':
			ans.append(i + 1)
	if ans:
		print(1)
		print(len(ans), end=' ')
		print(*ans)
	else:
		print(0)


for _ in range(int(input())):
	(_, line) = (input(), input())
	count_one = line.count('1')
	index_change = [i for (i, el) in enumerate(line, 1) if i <= len(line) - count_one and el == '1' or (i > len(line) - count_one and el == '0')]
	if len(index_change) != 0:
		print(1)
		print(len(index_change), *index_change)
	else:
		print(0)


n = int(input())
for i in range(n):
	x = int(input())
	s0 = input()
	s1 = [int(i) for i in str(s0)]
	s2 = sorted(s1)
	ans = []
	for i in range(len(s1)):
		if s1[i] != s2[i]:
			ans.append(i + 1)
	if len(ans) == 0:
		print(0)
	else:
		print(1)
		print(len(ans), end=' ')
		print(' '.join(map(str, ans)))


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	sort_s = ''.join(sorted(s))
	index = []
	for i in range(n):
		if s[i] != sort_s[i]:
			index.append(i + 1)
	if len(index) == 0:
		print(0)
	else:
		print(1)
		print(len(index), end=' ')
	for i in index:
		print(i, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	l1 = []
	l = ''.join(sorted(s))
	for i in range(len(s)):
		if s[i] != l[i]:
			l1.append(i)
	if len(l1) == 0:
		print(0)
	else:
		print(1)
	if len(l1) > 0:
		print(len(l1), end=' ')
	for i in l1:
		print(i + 1, end=' ')


def solve(n, s):
	if s == sorted(s):
		print(0)
		return
	j = n - 1
	while j >= 0 and s[j] == '1':
		j -= 1
	i = 0
	while i < n and s[i] == '0':
		i += 1
	ans = []
	while i < j and j >= 0 and (i < n):
		if s[i] == '1' and s[j] == '0':
			ans.append(i + 1)
			ans.append(j + 1)
			i += 1
			j -= 1
		else:
			if s[i] == '0':
				i += 1
			if s[j] == '1':
				j -= 1
	ans = [len(ans)] + sorted(ans)
	print(1)
	print(*ans)
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	solve(n, s)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = str(input())
	b = list(a)
	m = 0
	for x in b:
		m += '1' == x
	m = n - m
	res = []
	for i in range(n):
		if i < m:
			if b[i] == '1':
				res.append(i)
		elif b[i] == '0':
			res.append(i)
	if len(res) == 0:
		print(0)
		continue
	print(1)
	print(len(res), end=' ')
	for x in res:
		print(x + 1, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	sort = sorted(string)
	misplace = []
	for i in range(n):
		if string[i] != sort[i]:
			misplace.append(i + 1)
	if len(misplace):
		print(1)
		print(len(misplace), end=' ')
		print(*misplace)
	else:
		print(0)


def flip(st):
	i1 = st.index(1)
	st.reverse()
	i2 = st.index(0)
	st.reverse()
	i2 = n - i2 - 1
	temp = st[i1]
	st[i1] = st[i2]
	st[i2] = temp
	return (i1, i2, st)
N = int(input())
for i in range(N):
	sub = []
	n = int(input())
	s = list(input())
	s = [int(s[i]) for i in range(n)]
	c = 0
	while s != sorted(s):
		(a, b, s) = flip(s)
		sub = sub + [a, b]
		c = c + 1
	print(int(bool(c)), '\n')
	sub.sort()
	if bool(c):
		print(len(sub), end=' ')
		for i in range(len(sub)):
			print(sub[i] + 1, end=' ')
		print('\n')


for i in range(int(input())):
	n = int(input())
	string = input()
	ans = []
	low = 0
	high = n - 1
	cnt = 0
	while low <= high:
		if string[low] == '1':
			while string[high] == '1' and high > low:
				high -= 1
			if string[high] == '0':
				ans.append(low + 1)
				ans.append(high + 1)
				high -= 1
				cnt += 2
		low += 1
	if ans == []:
		print(0)
	else:
		print(1)
		print(cnt, end=' ')
		for j in range(0, cnt, 2):
			print(ans[j], end=' ')
		for j in range(cnt - 1, -1, -2):
			print(ans[j], end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(input())
	c = sorted(a)
	ans = 0
	one = a.count('1')
	two = a.count('0')
	ck = []
	for j in range(n - 1):
		if a == c:
			break
		ans += 1
		now = 0
		rep = []
		for i in range(n - one, n):
			if a[i] == '0':
				rep.append(i)
				now += 1
		ll = now
		for i in range(two):
			if a[i] == '1':
				rep.append(i)
				ll -= 1
		rep.sort()
		ck.append(rep)
		for i in range(len(rep) // 2):
			(a[rep[i]], a[rep[len(rep) - i - 1]]) = (a[rep[len(rep) - i - 1]], a[rep[i]])
	print(ans)
	for i in ck:
		print(len(i), end=' ')
		for j in i:
			print(j + 1, end=' ')
		print()


for t in range(int(input())):
	l = int(input())
	s = input()
	zC = 0
	for i in s:
		if i == '0':
			zC += 1
	yadda = []
	for i in range(0, zC):
		if s[i] == '1':
			yadda.append(i + 1)
	for i in range(zC, l):
		if s[i] == '0':
			yadda.append(i + 1)
	if len(yadda) == 0:
		print(0)
	else:
		print(1)
		print(len(yadda), ' '.join([str(i) for i in yadda]))


n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	left = 0
	left_idxes = []
	right = m - 1
	right_idxes = []
	while left <= right:
		while left <= right and s[right] == '1':
			right -= 1
		while left <= right and s[left] == '0':
			left += 1
		if left <= right and s[left] == '1' and (s[right] == '0'):
			left_idxes.append(str(left + 1))
			right_idxes.append(str(right + 1))
			left += 1
			right -= 1
	if len(left_idxes) == 0:
		print('0')
	else:
		print('1')
		right_idxes.reverse()
		print('{} {}'.format(len(left_idxes) * 2, ' '.join(left_idxes + right_idxes)))


t = int(input())
for tc in range(t):
	n = int(input())
	ch = str(input())
	ct1 = 0
	for i in range(n):
		if ch[i] == '1':
			ct1 = ct1 + 1
	ct0 = 0
	ls = list()
	for i in range(ct1):
		if ch[n - i - 1] == '0':
			ct0 = ct0 + 1
			ls.append(n - i)
	if ct0 == 0:
		print(0)
	else:
		print(1)
		print(ct0 * 2, end=' ')
		ls.reverse()
		lp = ct0
		j = 0
		while lp > 0:
			if ch[j] == '1':
				print(j + 1, end=' ')
				lp = lp - 1
			j = j + 1
		for i in range(ct0):
			print(ls[i], end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	k = ''.join(sorted(s))
	a = []
	for i in range(len(s)):
		if s[i] != k[i]:
			a.append(i)
	val = 1 if len(a) > 0 else 0
	print(val)
	if val > 0:
		print(len(a), end=' ')
	for j in range(len(a)):
		print(a[j] + 1, end=' ')
	print()


import math
for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = sorted(a)
	c = []
	if a == b:
		print(0)
	else:
		i = 0
		for x in a:
			if x != b[i]:
				c.append(i + 1)
			i += 1
		print(1)
		print(len(c), *c)


from sys import stdin
MOD = 10000000000.0 + 7

def rl() -> str:
	return stdin.readline().rstrip()

def ri() -> str:
	return int(rl())

def rii() -> str:
	return list(map(int, rl().split()))

def form(mean, dev):
	return abs(mean - dev)
t = ri()
for _ in range(t):
	n = ri()
	s = rl()
	ones = s.count('1')
	swaps = []
	for (i, e) in enumerate(s[:len(s) - ones]):
		if e == '1':
			swaps.append(str(i + 1))
	for (i, e) in enumerate(s[len(s) - ones:]):
		if e == '0':
			swaps.append(str(i + (len(s) - ones) + 1))
	if len(swaps) > 1:
		print(1)
		print(len(swaps), ' '.join(swaps))
	else:
		print(0)


def readint():
	return int(input())

def readarr():
	return list(map(int, input().split()))

def readmore():
	return map(int, input().split())

def main():
	t = readint()
	for _ in range(t):
		n = readint()
		s = input()
		(i, j) = (0, n - 1)
		i_list = []
		while i < j:
			if s[i] == '0':
				i += 1
				continue
			if s[j] == '1':
				j -= 1
				continue
			i_list.append(i + 1)
			i_list.append(j + 1)
			i += 1
			j -= 1
		k = len(i_list)
		if k > 0:
			print(1)
			i_list.sort()
			print(k, *i_list)
		else:
			print(0)
main()


import sys
import math

def II():
	return int(sys.stdin.readline())

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

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

def SI():
	return sys.stdin.readline().strip()

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def pow(n, exponent):
	if exponent == 0 or n == 1:
		return 1
	if exponent == 1:
		return n
	if exponent == -1:
		return 1 / n
	a = exponent // 2
	return pow(n, a) * pow(n, exponent - a)
for __ in range(II()):
	n = II()
	st = SI()
	arr = list(st)
	arr.sort()
	cost = 0
	ans = []
	for i in range(n):
		if arr[i] != st[i]:
			cost += 1
			ans.append(i + 1)
	if len(ans) == 0:
		print(0)
	else:
		print(1)
		print(len(ans), *ans)


x = int(input())
for t in range(x):
	n = int(input())
	s = input()
	ls = sorted(s)
	ans = []
	for i in range(len(ls)):
		if s[i] != ls[i]:
			ans.append(i + 1)
	if len(ans) == 0:
		print(0)
	else:
		print(1)
		print(len(ans), end=' ')
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def reverseSort(self, binary: str) -> None:
		ptr1 = 0
		ptr2 = len(binary) - 1
		ans = []
		while ptr1 < ptr2:
			if binary[ptr1] == '1' and binary[ptr2] == '0':
				ans.append(ptr1 + 1)
				ans.append(ptr2 + 1)
				ptr1 += 1
				ptr2 -= 1
			elif binary[ptr1] == '0':
				ptr1 += 1
			elif binary[ptr2] == '1':
				ptr2 -= 1
		if len(ans) == 0:
			print(0)
		else:
			print(1)
			print(len(ans), *sorted(ans))
obj = Solution()
t = int(input())
for _ in range(t):
	n = int(input())
	binary = input()
	obj.reverseSort(binary)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	s1 = sorted(s)
	ans = []
	for i in range(n):
		if s[i] != s1[i]:
			ans.append(i + 1)
	ans.insert(0, len(ans))
	if ans[0] == 0:
		print(*ans)
	else:
		print(1)
		print(*ans)


t = int(input())
for j in range(t):
	n = int(input())
	a = input()
	a = [int(i) for i in a]
	s = sum(a)
	d = []
	for j in range(n - s):
		if a[j] == 1:
			d.append(j + 1)
	for j in range(n - s, n):
		if a[j] == 0:
			d.append(j + 1)
	if len(d) == 0:
		print(0)
	else:
		print(1)
		print(len(d), *d)


import collections
import math
t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	s1 = []
	(left, right) = (0, n - 1)
	move = 1
	while left <= right:
		if s[left] == '1' and s[right] == '0':
			s1.append(left)
			s1.append(right)
			left += 1
			right -= 1
		elif s[left] == '0':
			left += 1
		elif s[right] == '1':
			right -= 1
	if len(s1) == 0:
		print(0)
	else:
		s1.sort()
		print(move)
		print(len(s1), end=' ')
		for i in s1:
			print(i + 1, end=' ')
		print('\r')


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	srtd = ''.join(sorted(s))
	ans = []
	for i in range(len(s)):
		if s[i] != srtd[i]:
			ans.append(i)
	flag = 1 if len(ans) > 0 else 0
	print(flag)
	if flag > 0:
		print(len(ans), end=' ')
	for i in range(len(ans)):
		print(ans[i] + 1, end=' ')
	print()


for j in range(int(input())):
	n = int(input())
	s = list(input())
	ss = sorted(s)
	if s == ss:
		print(0)
	else:
		print(1)
		l = [i + 1 for i in range(n) if s[i] != ss[i]]
		print(len(l), *l)


for _ in range(int(input())):
	n = int(input())
	s = input()
	res = ['0'] * s.count('0') + ['1'] * s.count('1')
	i = []
	for x in range(n):
		if s[x] != res[x]:
			i.append(x + 1)
	if i:
		print(1)
		print(len(i), end=' ')
		print(*i)
	else:
		print(0)


for _ in range(int(input())):
	x = int(input())
	y = list(input())
	s = sorted(y)
	if y == s:
		print(0)
	else:
		print(1)
		l = []
		for i in range(len(y)):
			if y[i] != s[i]:
				l.append(i + 1)
		print(len(l), end=' ')
		print(*l)


for u in range(int(input())):
	(n, s) = (int(input()), ' ' + input())
	(c, lst) = (s.count('1'), [])
	for x in range(n, n - c, -1):
		if s[x] == '0':
			lst.append(x)
	if len(lst) == 0:
		print(0)
	else:
		print(1)
		for x in range(n - c, 0, -1):
			if s[x] == '1':
				lst.append(x)
		print(len(lst), *lst[::-1])


test = int(input())
for _ in range(test):
	n = int(input())
	astring = input()
	zeros = astring.count('0')
	ans = []
	for i in range(zeros):
		if astring[i] == '1':
			ans.append(i + 1)
	for j in range(zeros, n):
		if astring[j] == '0':
			ans.append(j + 1)
	x = len(ans)
	if x > 0:
		print(1)
		print(x, *ans)
	else:
		print(x)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	l = list(s)
	l1 = sorted(l)
	if l == l1:
		print(0)
	else:
		k = []
		for i in range(n):
			if s[i] != l1[i]:
				k.append(i + 1)
		k.insert(0, len(k))
		print(1)
		for i in range(len(k)):
			print(k[i], end=' ')
		print()


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	s = list(sys.stdin.readline().strip())
	sorted_string = ''.join(sorted(s))
	res = []
	for i in range(len(s)):
		if s[i] != sorted_string[i]:
			res.append(i)
	if len(res) > 0:
		print(1)
		print(len(res), end=' ')
		print(' '.join(map(lambda x: str(x + 1), res)))
	else:
		print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(input())
	rlst = lst[::-1]
	try:
		if lst.index('1') > n - rlst.index('0') - 1:
			print(0)
		else:
			ans = []
			while lst.index('1') < n - rlst.index('0') - 1:
				one = lst.index('1')
				zero = n - rlst.index('0') - 1
				ans.append(one + 1)
				ans.append(zero + 1)
				(lst[one], lst[zero]) = (lst[zero], lst[one])
				rlst = lst[::-1]
			ans.sort()
			print(1)
			print(len(ans), end=' ')
			print(*ans)
	except ValueError:
		print(0)


for _ in range(int(input())):
	n = int(input())
	s = input()
	rev = ''.join(sorted(s))
	if s != rev:
		print(1)
		c = 0
		ans = []
		for i in range(n):
			if s[i] != rev[i]:
				c += 1
				ans.append(i + 1)
		print(c, *ans)
	else:
		print(0)


for z in range(int(input())):
	n = int(input())
	s = input()
	s1 = ''.join(sorted(s))
	d = 0
	for _ in range(len(s)):
		if s[_] != s1[_]:
			d += 1
	if d == 0:
		print(0)
	else:
		print(1)
		print(d, end=' ')
		for _ in range(len(s1)):
			if s[_] != s1[_]:
				print(_ + 1, end=' ')


import sys
input = sys.stdin.readline

def solve(n, s):
	(front, back) = (0, n - 1)
	res = []
	while front < back:
		if s[back] == '1':
			back -= 1
		elif s[front] == '0':
			front += 1
		else:
			(f, b) = ([], [])
			while front < back:
				if s[front] == '0':
					front += 1
					continue
				elif s[back] == '1':
					back -= 1
					continue
				b.append(back + 1)
				f.append(front + 1)
				back -= 1
				front += 1
			if len(f) > 0 and len(b) > 0:
				res.append([len(f) + len(b)] + f + b[::-1])
	print(len(res))
	for each in res:
		print(*each)
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	solve(n, s)


tcs = int(input())
for i in range(tcs):
	ln = int(input())
	st = list(map(int, input()))
	if sorted(st) == st:
		print(0)
	else:
		finalIndexes = []
		members = 0
		numZeros = st.count(0)
		numOnes = st.count(1)
		for i in range(numZeros):
			if st[i] == 1:
				finalIndexes.append(i + 1)
				members += 1
		for i in range(numZeros, ln):
			if st[i] == 0:
				finalIndexes.append(i + 1)
				members += 1
		print(1)
		print(members, *finalIndexes)


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = list(b)
	x = sorted(c)
	y = []
	if c == x:
		print(0)
	else:
		for i in range(len(c)):
			if c[i] != x[i]:
				y.append(i + 1)
		print(1)
		print(len(y), *y)


cases = int(input())
while cases > 0:
	n = int(input())
	p = list(input())
	t = p.copy()
	tot = 0
	count1 = p.count('1')
	for i in reversed(range(0, n)):
		if p[i] == '0' and n - count1 <= i:
			t[i] = '1'
			tot += 2
		elif p[i] == '1' and n - count1 > i:
			t[i] = '0'
	if p == t:
		print(0)
	else:
		print(1)
		print(tot, end=' ')
		for i in range(n):
			if p[i] != t[i]:
				print(i + 1, end=' ')
		print()
	cases -= 1


import sys
input = sys.stdin.readline

def check(S):
	last_0 = -1
	already = 0
	first_1 = 0
	for (i, x) in enumerate(S):
		if x == '0':
			last_0 = i
		elif already == 1:
			continue
		else:
			first_1 = i
			already = 1
	return last_0 < first_1
T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	if check(s):
		print(0)
	else:
		zero_index = n - 1
		one_index = 0
		onehalf = []
		zerohalf = []
		while one_index < zero_index:
			while one_index < n and s[one_index] != '1':
				one_index += 1
			while zero_index >= 0 and s[zero_index] != '0':
				zero_index -= 1
			if one_index >= zero_index:
				break
			onehalf.append(one_index + 1)
			zerohalf.append(zero_index + 1)
			one_index += 1
			zero_index -= 1
		print(1)
		print(len(onehalf) + len(zerohalf), end=' ')
		for x in onehalf:
			print(x, end=' ')
		for x in reversed(zerohalf):
			print(x, end=' ')
		print()


import math
t = int(input())
while t > 0:
	n = int(input())
	k = [int(x) for x in input()]
	i = 0
	j = n - 1
	l = []
	while i < j:
		if k[i] == 0:
			i = i + 1
		elif k[j] == 1:
			j = j - 1
		else:
			l.append([i, j])
			i = i + 1
			j = j - 1
	if len(l) > 0:
		print(1)
		print(len(l * 2), end=' ')
		for i in l:
			print(i[0] + 1, end=' ')
		for i in l[::-1]:
			print(i[1] + 1, end=' ')
		print()
	else:
		print(0)
	t = t - 1