A. Циншань любит строки 2
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Циншань есть строка $$$s$$$, которая содержит только $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

Строка $$$a$$$ длины $$$k$$$ является хорошей тогда и только тогда, когда

  • $$$a_i \ne a_{k-i+1}$$$ для всех $$$i=1,2,\ldots,k$$$.

Для участников Div. 2: обратите внимание, что это условие отличается от условия в задаче B.

Например, $$$\texttt{10}$$$, $$$\texttt{1010}$$$, $$$\texttt{111000}$$$ — хорошие строки, а $$$\texttt{11}$$$, $$$\texttt{101}$$$, $$$\texttt{001}$$$, $$$\texttt{001100}$$$ — плохие.

Циншань хочет сделать $$$s$$$ хорошей. Для этого она может проделать следующую операцию не более $$$300$$$ раз (возможно, ноль):

  • вставить $$$\texttt{01}$$$ в любое место строки $$$s$$$ (получив новую строку $$$s$$$).

Скажите, возможно ли сделать $$$s$$$ хорошей. Если это возможно, то приведите последовательность операций, которая делает строку $$$s$$$ хорошей.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$.

Гарантируется, что $$$s$$$ состоит только из $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

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

Для каждого набора входных данных, если невозможно сделать $$$s$$$ хорошей, выведите $$$-1$$$.

В противном случае в первой строке выведите $$$p$$$ ($$$0 \le p \le 300$$$) — количество операций.

Затем выведите $$$p$$$ целых чисел во второй строке. Целое число $$$i$$$ должно быть индексом $$$x_i$$$ ($$$0 \le x_i \le n+2i-2$$$) — позицией, в которую необходимо вставить $$$\texttt{01}$$$ в текущем $$$s$$$. Если $$$x_i=0$$$, то $$$\texttt{01}$$$ вставляется в начало $$$s$$$. В противном случае, $$$\texttt{01}$$$ вставляется сразу после $$$x_i$$$-го символа $$$s$$$.

Можно показать, что при данных ограничениях, если ответ существует, то всегда найдется ответ, требующий не более $$$300$$$ операций.

Пример
Входные данные
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
Выходные данные
0

-1
-1
2
6 7
1
10
-1
Примечание

В первом наборе входных данных можно выполнить ноль операций и получить $$$s=\texttt{01}$$$, что является хорошей строкой.

Другим правильным решением является выполнение одной операции: (вставленная $$$\texttt{01}$$$ подчеркнута)

  1. $$$\texttt{0}\underline{\texttt{01}}\texttt{1}$$$

получаем $$$s = \texttt{0011}$$$, что является хорошей строкой.

Во втором и третьем наборах входных данных сделать $$$s$$$ хорошей невозможно.

В четвертом наборе входных данных можно выполнить две операции:

  1. $$$\texttt{001110}\underline{\texttt{01}}$$$
  2. $$$\texttt{0011100}\underline{\texttt{01}}\texttt{1}$$$

и получить $$$s = \texttt{0011100011}$$$, что является хорошей строкой.