C. Лед и пламень
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Little09 и его друзья играют в игру. Есть $$$n$$$ игроков, и значение температуры игрока $$$i$$$ равно $$$i$$$.

Типы окружающей среды обозначаются как $$$0$$$ или $$$1$$$. Когда два игрока сражаются в определенной среде, если её тип равен $$$0$$$, то всегда побеждает игрок с более низким значением температуры; если он равен $$$1$$$, то всегда побеждает игрок с более высоким значением температуры. Типы этих сред $$$n-1$$$ образуют бинарную строку $$$s$$$ длиной $$$n-1$$$.

Если в игре участвует $$$x$$$ игроков, то всего будет $$$x-1$$$ сражений, а типами $$$x-1$$$ сред будут первые $$$x-1$$$ символов $$$s$$$. Если в турнире осталось более одного игрока, выберите для сражения любых двух оставшихся игроков. Игрок, который проиграет, выбывает из турнира. Типом среды для $$$i$$$-го сражения является $$$s_i$$$.

Для каждого $$$x$$$ от $$$2$$$ до $$$n$$$ ответьте на следующий вопрос: если в игре участвуют все игроки, значение температуры которых не превышает $$$x$$$, то сколько игроков имеют шансы на победу?

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$)  — количество игроков.

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длиной $$$n-1$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$3\cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n-1$$$ целых чисел  — для каждого $$$x$$$ от $$$2$$$ до $$$n$$$ выведите количество игроков, имеющих шанс на победу.

Пример
Входные данные
2
4
001
4
101
Выходные данные
1 1 3 
1 2 3
Примечание

В первом наборе входных данных для $$$x=2$$$ и $$$x=3$$$ победителем может стать только игрок, чье значение температуры равно $$$1$$$. Для $$$x=4$$$ победителем могут стать игроки, чьи значения температуры равны $$$2,3,4$$$.