Description

deepl翻译

青山有一串 $s$ ，其中只包含 $\texttt{0}$ 和 $\texttt{1}$ 。

长度为 $k$ 的字符串 $a$ 是好字符串，当且仅当

• $a_i \ne a_{k-i+1}$ 为所有的 $i=1,2,\ldots,k$ 。

对于第 2 组的参赛者，请注意这一条件与问题 B 中的条件不同。

例如， $\texttt{10}$ 、 $\texttt{1010}$ 、 $\texttt{111000}$ 是好题，而 $\texttt{11}$ 、 $\texttt{101}$ 、 $\texttt{001}$ 、 $\texttt{001100}$ 不是好题。

青山想让 $s$ 变好。为此，她最多可以***做以下操作 $300$ 次（可能为零）：

• 在 $s$ 的任意位置插入 $\texttt{01}$ （得到一个新的 $s$ ）。

请告诉青山，是否有可能使 $s$ 变好。如果可能，请打印出使 $s$ 变好的操作序列。

Input

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

The first line of each test case contains a single integer $n$ ($1 \le n\le 100$) — the length of string $s$, respectively.

The second line of each test case contains a string $s$ with length $n$.

It is guaranteed that $s$ only consists of $\texttt{0}$ and $\texttt{1}$.

Output

For each test case, if it impossible to make $s$ good, output $-1$.

Otherwise, output $p$ ($0 \le p \le 300$) — the number of operations, in the first line.

Then, output $p$ integers in the second line. The $i$-th integer should be an index $x_i$ ($0 \le x_i \le n+2i-2$) — the position where you want to insert $\texttt{01}$ in the current $s$. If $x_i=0$, you insert $\texttt{01}$ at the beginning of $s$. Otherwise, you insert $\texttt{01}$ immediately after the $x_i$-th character of $s$.

We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most $300$ operations.

6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001

0

-1
-1
2
6 7
1
10
-1

Note

In the first test case, you can do zero operations and get $s=\texttt{01}$, which is good.

Another valid solution is to do one operation: (the inserted $\texttt{01}$ is underlined)

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

and get $s = \texttt{0011}$, which is good.

In the second and the third test case, it is impossible to make $s$ good.

In the fourth test case, you can do two operations:

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

and get $s = \texttt{0011100011}$, which is good.