Abbey Road

Cerință

C. este proprietara cafenelei Abbey Road de pe strada cu același nume din Londra. Deasupra intrării în Abbey Road se află un semn cu $N$ becuri galbene, care pot fi aprinse sau stinse, numerotate de la $0$ la $N - 1$. Pentru simplitate, în continuare vom reprezenta stările becurilor printr-un șir binar $S$, unde $S[i]$ descrie starea celui de-al $i$-lea bec: $0$ dacă e stins și $1$ dacă e aprins.

Definim un fragment al semnului drept o subsecvență maximală a sa în care toate becurile au aceeași stare. De exemplu, șirul de becuri $111100111011$ se împarte în fragmente astfel: $1111|00|111|0|11$.

C. e de părere că becurile trebuie să aibă o configurație cu număr maxim de fragmente, deoarece ar atrage mai mulți clienți. Starea unui bec se poate modifica apăsând un buton aflat în spatele său.

Din păcate, C. este cam scundă și nu ajunge la butoane. Singura metodă prin care ea poate apăsa pe butoane este cu ajutorul unui băț bifurcat, cu care poate doar să apese, simultan, pe butoanele $i$ și $i+1$, unde $0 \leq i \leq N ‑ 2$.
C. nu își dă seama cum să apese pe butoane ca să obțină o configurație cu număr maxim de fragmente a becurilor, așa că vă cere ajutorul.

Pentru a obține puncte pentru un test, este nevoie ca șirul să conțină cel puțin $\lfloor \frac{N}{2} \rfloor$ fragmente. Dacă șirul nu conține numărul maxim de fragmente, veți primi un punctaj între 30 și 70 de puncte, în funcție de cât de departe sunteți de numărul maxim de fragmente care se pot obține pe acel test.

Date de intrare

Pe prima linie din input se găsește numărul $T$ - numărul de scenarii care trebuie rezolvate. Pentru fiecare dintre aceste scenarii, formatul de intrare este următorul:

Pe prima linie se găsește numărul $N$. Pe a doua linie se găsește șirul $S$.

Date de ieșire

Pentru fiecare dintre cele $T$ teste, formatul de ieșire este următorul:

Pe prima linie se va afișa $M$ ($0 \leq M \leq N$) - numărul de operații necesare. Pe a doua linie se vor afișa $M$ numere din intervalul $[0, N - 2]$, reprezentând indicele $i$ pentru fiecare operație.

Scorul unui fișier de test se va considera minimul dintre scorurile celor $T$ test din el. Dacă notăm cu $x$ numărul de fragmente din soluția concurentului și cu $y$ numărul de fragmente maxim care se poate obține, formula pentru scor este următoarea:

Dacă există mai multe soluții, se poate afișa oricare.

Restricții și precizări

• $2 \leq N \leq 10^6$;
• Suma valorilor lui $N$ pe fiecare test nu va depăși $10^6$;
• Pentru teste în valoare de $15$ puncte, $S_0 = S_1 = \dots = S_{N - 1}$;
• Pentru teste în valoare de alte $14$ puncte, $N \leq 2$;
• Pentru teste în valoare de alte $25$ puncte, $N \leq 15$;
• Pentru teste în valoare de alte $17$ puncte, $N \leq 2^6$;

Exemplul 1

stdin

2
4
0101
4
0000

stdout

0
2
0 1

Explicație

Pentru primul șir, avem deja numărul maxim de fragmente pe care îl putem obține.

Pentru cel de al doilea șir, aplicăm operația pe poziția $1$, șirul devenind $1100$. Aplicăm din nou operația pe poziția $1$, șirul devenind $1010$. Aceset șir are număr maxim de fragmente.