Busy Beaver postanowił kandydować na prezydenta. Niestety, jego jedyny rywal, Leniwy Lemur, jest zbyt silny i Busy Beaver nie może wygrać w uczciwy sposób. Dlatego robi to, co robią wszyscy dobrzy politycy: ustawia wybory poprzez gerrymandering!

Kraj Busy Beavera składa się z $N$ miast ustawionych w rzędzie, ponumerowanych od $1$ do $N$. Każde miasto głosuje na Leniwego Lemura lub Busy Beavera, co jest reprezentowane przez $0$, jeśli głos jest na Leniwego Lemura, oraz $1$, jeśli głos jest na Busy Beavera. Busy Beaver może podzielić $N$ miast na $K$ niepustych bloków sąsiadujących ze sobą miast, gdzie każdy blok stanowi okręg wyborczy. Dla każdej wartości $K$ od $1$ do $N$, Busy Beaver chce zmaksymalizować liczbę okręgów, w których uzyskał ściśle więcej głosów niż Leniwy Lemur.

Czy możesz pomóc Busy Beaverowi znaleźć maksymalną liczbę okręgów ze ściśle większą liczbą głosów dla $K = 1, \dots, N$?

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $T$ ($1 \le T \le 10^4$). Następnie następuje opis przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera jedną liczbę całkowitą $N$ ($1 \le N \le 10^5$) określającą liczbę miast.

Druga linia każdego przypadku testowego zawiera ciąg $s$ złożony z $0$ i $1$ o długości $N$, gdzie $s_i$ równe $0$ oznacza, że Leniwy Lemur wygrywa głosowanie w $i$-tym mieście, a $1$ oznacza, że Busy Beaver wygrywa głosowanie w $i$-tym mieście, dla każdego $i$ od $1$ do $N$.

Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz $N$ liczb całkowitych, gdzie $K$-ta liczba reprezentuje maksymalną liczbę okręgów ze ściśle większą liczbą głosów dla Busy Beavera po podziale miast na $K$ niepustych bloków sąsiadujących ze sobą miast.

Podzadania

• ($10$ punktów) Suma $N$ we wszystkich przypadkach testowych wynosi co najwyżej $100$.
• ($25$ punktów) Suma $N$ we wszystkich przypadkach testowych wynosi co najwyżej $3000$.
• ($65$ punktów) Suma $N$ we wszystkich przypadkach testowych wynosi co najwyżej $10^5$.

Przykład

Przykład 1

3
3
000
5
01101
8
11011011

Wyjście 1

0 0 0
1 1 2 2 3
1 2 3 4 4 5 5 6

Uwagi

Istnieją $3$ przypadki testowe.

W pierwszym przypadku testowym Busy Beaver nigdy nie może wygrać żadnego okręgu, ponieważ każde miasto głosuje na Leniwego Lemura.

W drugim przypadku testowym jest $5$ miast. Dla $K = 3$, Busy Beaver może wygrać $2$ okręgi, dzieląc miasta na podtablice $[1, 3]$, $[4, 4]$ oraz $[5, 5]$. W $[1, 3]$, $2$ z $3$ miast głosują na niego. Przegrywa w podtablicy $[4, 4]$, ponieważ jedyne miasto w niej nie głosuje na niego. Wygrywa w podtablicy $[5, 5]$, ponieważ jedyne miasto w niej głosuje na niego. Można udowodnić, że Busy Beaver nie może wygrać więcej niż $2$ okręgów.

Zauważ, że podział na podtablice $[1, 2]$, $[3, 4]$ oraz $[5, 5]$ przyniósłby mu tylko $1$ wygrany okręg. W szczególności, wygrywa tylko w jednym mieście w każdym z okręgów $[1, 2]$ oraz $[3, 4]$, a zatem nie posiada ścisłej większości w żadnym z nich.