[Solution] Qingshan Loves Strings 2 Solution Codeforces

Qingshan has a string $s$ which only contains $0$ and $1$ .

A string $a$ of length $k$ is good if and only if

$a_{i} \neq a_{k - i + 1}$ for all $i = 1, 2, \dots, k$ .

For Div. 2 contestants, note that this condition is different from the condition in problem B.

For example, $10$ , $1010$ , $111000$ are good, while $11$ , $101$ , $001$ , $001100$ are not good.

Qingshan wants to make $s$ good. To do this, she can do the following operation at most $300$ times (possibly, zero):

insert $01$ to any position of $s$ (getting a new $s$ ).

Please tell Qingshan if it is possible to make $s$ good. If it is possible, print a sequence of operations that makes $s$ good.

Input [Solution] Qingshan Loves Strings 2 Solution Codeforces

The input consists of multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 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 \leq n \leq 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 $0$ and $1$ .

Output [Solution] Qingshan Loves Strings 2 Solution Codeforces$

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

Otherwise, output $p$ ( $0 \leq p \leq 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 \leq x_{i} \leq n + 2 i - 2$ ) — the position where you want to insert $01$ in the current $s$ . If $x_{i} = 0$ , you insert $01$ at the beginning of $s$ . Otherwise, you insert $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.

Example

input

Copy

000

1111

001110

0111001100

001

output

Copy

Note [Solution] Qingshan Loves Strings 2 Solution Codeforces

In the first test case, you can do zero operatiaon and get $s = 01$ , which is good.

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

$0 \underline{01} 1$

and get $s = 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:

$001110 \underline{01}$
$0011100 \underline{01} 1$

and get $s = 0011100011$ , which is good.