Busy Beaver a décidé de se présenter à l'élection présidentielle. Malheureusement, son seul rival, Lazy Lemur, est trop puissant, et Busy Beaver ne peut pas gagner par des moyens conventionnels. Il fait donc ce que font tous les bons politiciens : truquer l'élection par charcutage électoral !

Le pays de Busy Beaver se compose de $N$ villes alignées, numérotées de $1$ à $N$. Chaque ville vote soit pour Lazy Lemur, soit pour Busy Beaver, représenté par un $0$ si le vote est pour Lazy Lemur et un $1$ si le vote est pour Busy Beaver. Cependant, Busy Beaver peut diviser les $N$ villes en $K$ blocs non vides de villes contiguës, chaque bloc constituant un district. Pour chaque valeur de $K$ allant de $1$ à $N$, Busy Beaver souhaite maximiser le nombre de districts ayant strictement plus de votes pour lui que pour Lazy Lemur.

Pouvez-vous aider Busy Beaver à trouver le nombre maximum de districts ayant strictement plus de votes pour $K = 1, \dots, N$ ?

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $T$ ($1 \le T \le 10^4$). La description des cas de test suit.

La première ligne de chaque cas de test contient un entier $N$ ($1 \le N \le 10^5$) décrivant le nombre de villes.

La deuxième ligne de chaque cas de test contient une chaîne $s$ de $0$ et de $1$ de longueur $N$, où $s_i$ étant $0$ indique que Lazy Lemur remporte le vote de la $i^\text{ème}$ ville et $1$ indique que Busy Beaver remporte le vote de la $i^\text{ème}$ ville, pour chaque $i$ de $1$ à $N$.

Il est garanti que la somme de $N$ sur tous les cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez $N$ entiers, où le $K^\text{ème}$ entier représente le nombre maximum de districts ayant strictement plus de votes pour Busy Beaver après avoir divisé les villes en $K$ blocs non vides de villes contiguës.

Barème

• ($10$ points) La somme de $N$ sur tous les cas de test est au plus $100$.
• ($25$ points) La somme de $N$ sur tous les cas de test est au plus $3000$.
• ($65$ points) La somme de $N$ sur tous les cas de test est au plus $10^5$.

Exemples

Entrée 1

3
3
000
5
01101
8
11011011

Sortie 1

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

Remarque

Il y a $3$ cas de test.

Dans le premier cas de test, Busy Beaver ne peut jamais gagner de districts car chaque ville vote pour Lazy Lemur.

Dans le deuxième cas de test, il y a $5$ villes. Pour $K = 3$, Busy Beaver peut gagner $2$ districts en divisant les villes en districts en utilisant les sous-tableaux $[1, 3]$, $[4, 4]$ et $[5, 5]$. Dans $[1, 3]$, $2$ villes sur $3$ votent pour lui. Il perd le sous-tableau $[4, 4]$ car la seule ville qui s'y trouve ne vote pas pour lui. Il gagne le sous-tableau $[5, 5]$ car la seule ville qui s'y trouve vote pour lui. Il peut être prouvé que Busy Beaver ne peut pas gagner plus de $2$ districts.

Notez que diviser en sous-tableaux $[1, 2]$, $[3, 4]$ et $[5, 5]$ ne lui ferait gagner qu'un seul district. En particulier, il ne gagne qu'une seule ville dans chacun des sous-tableaux $[1, 2]$ et $[3, 4]$, et n'obtient donc pas une majorité stricte dans l'un ou l'autre de ces districts.