B. Дом с привидениями
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано число в двоичной системе счисления, состоящее из $$$n$$$ битов, возможно, с лидирующими нулями. Например, для $$$n = 5$$$ число $$$6$$$ задается как $$$00110$$$, а для $$$n = 4$$$ число $$$9$$$ задается как $$$1001$$$.

Фиксируем некоторое целое $$$i$$$, такое что $$$1 \le i \le n$$$. За одну операцию вы можете поменять местами любые два соседних элемента битовой записи. Ваша цель — найти наименьшее количество операций, за которое можно превратить исходное число в делящееся на $$$2^i$$$, или сказать, что это невозможно.

Обратите внимание, что для каждого $$$1 \le i \le n$$$ вы решаете задачу независимо.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину битовой записи числа.

Вторая строка каждого набора входных данных содержит строку длины $$$n$$$, состоящую из $$$0$$$ и $$$1$$$, — описание числа в двоичной системе счисления.

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

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

В каждом наборе входных данных для каждого $$$1 \le i \le n$$$ выведите наименьшее количество операций, необходимое для того, чтобы сделать число делящимся на $$$2^i$$$, или выведите $$$-1$$$, если это нельзя сделать.

Пример
Входные данные
6
1
1
2
01
3
010
5
10101
7
0000111
12
001011000110
Выходные данные
-1 
1 -1 
0 1 -1 
1 3 -1 -1 -1 
3 6 9 12 -1 -1 -1 
0 2 4 6 10 15 20 -1 -1 -1 -1 -1
Примечание

В первом наборе входных данных мы не можем менять элементы местами, и число $$$1$$$ не делится на $$$2$$$.

Во втором наборе входных данных исходное число равно $$$1$$$. Оно не делится на $$$2$$$, но если применить операцию, то получится число, в двоичной записи равное $$$10$$$, что в десятичной системе равно $$$2$$$, а значит, делится на $$$2$$$. Но на $$$4$$$ это число не делится, а с помощью операции нельзя получить других чисел.

В третьем наборе входных данных исходное число равно $$$2$$$. Для $$$i = 1$$$ операции применять не нужно, так как исходное число делится на $$$2$$$. Для $$$i = 2$$$ можно применить одну операцию, поменяв первые два бита местами (в двоичном представлении получим число $$$100$$$, которое задает число $$$4$$$). Для $$$i = 3$$$ ответа не существует.