F. Андрюша и CCB
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем красотой бинарной строки $$$z$$$ количество таких индексов $$$i$$$, что $$$1 \le i \lt |z|$$$ и $$$z_i \neq z_{i+1}$$$.

В ожидании своих приятелей из CCB Андрюша испек пирог, который представлен бинарной строкой $$$s$$$ длины $$$n$$$. Чтобы никого не обидеть, он хочет разделить эту строку на $$$k$$$ подстрок так, чтобы каждая цифра принадлежала ровно одной подстроке, и при этом красоты всех подстрок были одинаковы.

Андрюша не знает точного числа друзей из CCB, которые придут к нему домой. Поэтому он хочет найти количество значений $$$k$$$, при которых можно разбить пирог ровно на $$$k$$$ частей с одинаковыми красотами.

Однако Андрюшин брат, Тристан, решил, что в такой формулировке задача слишком простая. Поэтому он хочет, чтобы Вы нашли количество таких значений $$$k$$$ для каждого префикса строки. Другими словами, для каждого $$$i$$$ от $$$1$$$ до $$$n$$$, Вы должны найти количество значений $$$k$$$, при которых можно разбить префикс $$$s_1 s_2 \ldots s_i$$$ ровно на $$$k$$$ частей с одинаковыми красотами.

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

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

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

Вторая строка каждого набора данных содержит бинарную строку длины $$$n$$$, состоящую только из цифр 0 и 1.

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

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

Для каждого набора входных данных выведите одну строку, содержащую $$$n$$$ целых чисел $$$c_i$$$ ($$$0 \le c_i \le n$$$) — количество значений $$$k$$$, при которых можно разбить префикс $$$s_1 s_2 \ldots s_i$$$ ровно на $$$k$$$ частей с одинаковыми красотами.

Пример
Входные данные
3
5
00011
10
0101010101
7
0010100
Выходные данные
1 2 3 4 5
1 2 2 3 2 4 2 4 3 4
1 2 3 3 4 3 4
Примечание

В третьем наборе данных подходят следующие значения $$$k$$$:

  1. $$$i = 1$$$: $$$k \in \{1\}$$$,
  2. $$$i = 2$$$: $$$k \in \{1, 2\}$$$,
  3. $$$i = 3$$$: $$$k \in \{1, 2, 3\}$$$,
  4. $$$i = 4$$$: $$$k \in \{1, 3, 4\}$$$,
  5. $$$i = 5$$$: $$$k \in \{1, 2, 4, 5\}$$$,
  6. $$$i = 6$$$: $$$k \in \{1, 5, 6\}$$$,
  7. $$$i = 7$$$: $$$k \in \{1, 5, 6, 7\}$$$.