Let us define the beauty of a binary string $$$z$$$ as the number of indices $$$i$$$ such that $$$1 \le i \lt |z|$$$ and $$$z_i \neq z_{i+1}$$$.

While waiting for his friends from the CCB, Andryusha baked a pie, represented by a binary string $$$s$$$ of length $$$n$$$. To avoid offending anyone, he wants to divide this string into $$$k$$$ substrings such that each digit belongs to exactly one substring, and the beauties of all substrings are the same.

Andryusha does not know the exact number of friends from the CCB who will come to his house, so he wants to find the number of values of $$$k$$$ for which it is possible to split the pie into exactly $$$k$$$ parts with equal beauties.

However, Andryusha's brother, Tristan, decided that this formulation of the problem is too simple. Therefore, he wants you to find the number of such values of $$$k$$$ for each prefix of the string. In other words, for each $$$i$$$ from $$$1$$$ to $$$n$$$, you need to find the number of values of $$$k$$$ for which it is possible to split the prefix $$$s_1 s_2 \ldots s_i$$$ into exactly $$$k$$$ parts with equal beauties.

Input

Each test consists of several test cases. The first line of the input data contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of the binary string.

The second line of each test case contains a binary string of length $$$n$$$, consisting only of digits 0 and 1.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single line containing $$$n$$$ integers $$$c_i$$$ ($$$0 \le c_i \le n$$$) — the number of values of $$$k$$$ for which it is possible to split the prefix $$$s_1 s_2 \ldots s_i$$$ into exactly $$$k$$$ parts with equal beauties.

Note

In the third case, the values of $$$k$$$ that satisfy the conditions are:

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

Andryusha and CCB

Examples