# [ICPC2021 Nanjing R] Secret of Tianqiu Valley

## 题目描述

In the north tower of Tianqiu Valley's ruins, there are some flame torch puzzles and Lumine the traveler is facing the last and the hardest one. ![](https://cdn.luogu.com.cn/upload/image_hosting/sihi5us5.png) There are $n$ torches in a circle and some torches have been ignited initially. The $i$-th and the $(i \bmod n +1)$-th are adjacent for all $1 \le i \le n$. To solve the puzzle, all the torches should be ignited. In each move, Lumine can ignite an extinguished torch, and the status of the adjacent torches will be reversed affected by the supernatural. That is, each of the adjacent torches will be ignited if it is currently extinguished, or be extinguished if it is currently ignited. Time is money, Lumine wants to solve the puzzle in $2n$ moves or determine that the puzzle is unsolvable.

## 输入输出格式

### 输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line of the input contains an integer $n$ ($3 \le n \le 10^5$) indicating the number of torches in the circle. The second line contains a binary string $s_1s_2\cdots s_n$ of length $n$ ($s_i \in \{\text{0'}, \text{1'}\}$). If $s_i = \text{0'}$ the $i$-th torch is extinguished initially; If $s_i = \text{1'}$ the $i$-th torch is ignited initially. It is guaranteed that not all the torches have been ignited initially. It is also guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

### 输出格式

If the puzzle is unsolvable, output 0. Otherwise, output an integer $k$ $(1 \le k \le 2n)$ in the first line indicating the number of moves Lumine needs to solve the puzzle. Then output a line containing $k$ integers $t_1, t_2, \cdots, t_k$ separated by a space, where $t_i$ indicating that Lumine will ignite the $t_i$-th torch in the $i$-th move. If there are multiple answers print any of them. Please, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!

## 输入输出样例

### 输入样例 #1

2
5
00000
3
001


### 输出样例 #1

7
2 5 1 2 3 4 2
0


## 说明

For the first sample test case, the status of the torch will change like this: $00000$ $\to$ $11100$ $\to$ $01111$ $\to$ $10110$ $\to$ $01010$ $\to$ $00100$ $\to$ $00011$ $\to$ $11111$.