B. Красивая строка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная$$$^{\text{∗}}$$$ строка $$$s$$$ длины $$$n$$$.

Ваша задача — найти любую подпоследовательность$$$^{\text{†}}$$$ $$$p$$$ строки $$$s$$$ такую, что:

  • Подпоследовательность $$$p$$$ является неубывающей. То есть каждый символ $$$p$$$ не больше следующего.
  • Пусть $$$x$$$ обозначает строку, полученную путем удаления всех символов $$$p$$$ из $$$s$$$, сохраняя порядок оставшихся символов. Строка $$$x$$$ должна быть палиндромом$$$^{\text{‡}}$$$.

Вам нужно вывести любую допустимую подпоследовательность $$$p$$$, которая удовлетворяет обоим условиям. Если такой подпоследовательности не существует, выведите $$$-1$$$.

Обратите внимание, что пустая строка является как неубывающей, так и палиндромом.

$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая из символов '0' и '1'.

$$$^{\text{†}}$$$Подпоследовательность строки $$$s = s_1s_2\ldots s_n$$$ — это последовательность $$$p = s_{i_1}s_{i_2}\ldots s_{i_k}$$$ такая, что $$$1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$$$. Символы выбираются в порядке, но не обязательно смежно. Обратите внимание, что пустая строка является подпоследовательностью любой строки.

$$$^{\text{‡}}$$$Строка $$$t = t_1t_2\ldots t_m$$$ является палиндромом, если $$$t_i = t_{m - i + 1}$$$ для всех $$$1 \leq i \leq m$$$. Другими словами, строка читается одинаково вперед и назад.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 3000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10$$$) — длина строки.

Вторая строка содержит бинарную строку $$$s$$$ длиной $$$n$$$.

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

Если решение существует:

  • В первой строке выведите одно целое число $$$k$$$ ($$$0 \le k \le n$$$) — длина подпоследовательности $$$p$$$.
  • Во второй строке выведите $$$k$$$ различных целых чисел $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_1 \lt i_2 \lt \dots \lt i_k \le n$$$) — индексы символов в $$$s$$$, которые формируют $$$p$$$ (в порядке, как они появляются в $$$s$$$).

В противном случае выведите одну строку, содержащую $$$-1$$$.

Пример
Входные данные
5
3
010
3
001
5
00111
8
11010011
6
100101
Выходные данные
0

2
2 3
5
1 2 3 4 5
2
3 4
2
5 6
Примечание

В первом наборе входных данных мы удаляем пустую строку, в результате чего $$$x = \texttt{010}$$$, которая является палиндромом.

Во втором наборе входных данных мы удаляем $$$p = \texttt{01}$$$ (индексы $$$2$$$, $$$3$$$), в результате чего $$$x = \texttt{0}$$$, которая является палиндромом.

В третьем наборе входных данных мы удаляем $$$p = \texttt{00111}$$$ (индексы $$$1$$$ до $$$5$$$), в результате чего получается пустая строка, которая тривиально является палиндромом.

В четвертом наборе входных данных мы удаляем $$$p = \texttt{01}$$$ (индексы $$$3$$$, $$$4$$$), в результате чего $$$x = \texttt{110011}$$$, которая является палиндромом.

В пятом наборе входных данных мы удаляем $$$p = \texttt{01}$$$ (индексы $$$5$$$, $$$6$$$), в результате чего $$$x = \texttt{1001}$$$, которая является палиндромом.