Busy Beaver решил баллотироваться в президенты. К сожалению, его единственный соперник, Lazy Lemur, слишком силен, и Busy Beaver не может победить обычными средствами. Поэтому он делает то, что делают все хорошие политики: фальсифицирует выборы с помощью джерримендеринга!

Страна Busy Beaver состоит из $N$ городов, расположенных в ряд и пронумерованных от $1$ до $N$. В каждом городе голосуют либо за Lazy Lemur, либо за Busy Beaver, что представлено $0$, если голос отдан за Lazy Lemur, и $1$, если голос отдан за Busy Beaver. Однако Busy Beaver может разделить $N$ городов на $K$ непустых блоков из подряд идущих городов, где каждый блок является избирательным округом. Для каждого значения $K$ от $1$ до $N$ Busy Beaver хочет максимизировать количество округов, в которых голосов за него строго больше, чем за Lazy Lemur.

Помогите Busy Beaver найти максимальное количество округов со строго большим числом голосов за него для каждого $K = 1, \dots, N$.

Входные данные

Каждый тест содержит несколько тестовых случаев. Первая строка содержит количество тестовых случаев $T$ ($1 \le T \le 10^4$). Далее следует описание тестовых случаев.

Первая строка каждого тестового случая содержит одно целое число $N$ ($1 \le N \le 10^5$), описывающее количество городов.

Вторая строка каждого тестового случая содержит строку $s$ из $0$ и $1$ длиной $N$, где $s_i = 0$ означает, что Lazy Lemur победил в $i$-м городе, а $1$ означает, что Busy Beaver победил в $i$-м городе, для каждого $i$ от $1$ до $N$.

Гарантируется, что сумма $N$ по всем тестовым случаям не превышает $10^5$.

Выходные данные

Для каждого тестового случая выведите $N$ целых чисел, где $K$-е число представляет собой максимальное количество округов, в которых Busy Beaver получил строго больше голосов после разделения городов на $K$ непустых блоков из подряд идущих городов.

Оценка

• ($10$ баллов) Сумма $N$ по всем тестовым случаям не превышает $100$.
• ($25$ баллов) Сумма $N$ по всем тестовым случаям не превышает $3000$.
• ($65$ баллов) Сумма $N$ по всем тестовым случаям не превышает $10^5$.

Примеры

Входные данные 1

3
3
000
5
01101
8
11011011

Выходные данные 1

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

Примечание

Всего $3$ тестовых случая.

В первом тестовом случае Busy Beaver не может выиграть ни в одном округе, потому что в каждом городе голосуют за Lazy Lemur.

Во втором тестовом случае $5$ городов. Для $K = 3$ Busy Beaver может выиграть $2$ округа, разделив города на подмассивы $[1, 3]$, $[4, 4]$ и $[5, 5]$. В $[1, 3]$ $2$ из $3$ городов голосуют за него. Он проигрывает в подмассиве $[4, 4]$, так как единственный город там голосует не за него. Он выигрывает в подмассиве $[5, 5]$, так как единственный город там голосует за него. Можно доказать, что Busy Beaver не может выиграть более $2$ округов.

Заметьте, что разделение на подмассивы $[1, 2]$, $[3, 4]$ и $[5, 5]$ принесло бы ему победу только в $1$ округе. В частности, он выигрывает только в одном городе в каждом из подмассивов $[1, 2]$ и $[3, 4]$, и, следовательно, не имеет строгого большинства ни в одном из этих округов.