D. Eleven
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a binary string$$$^\dagger$$$ $$$S$$$ of length $$$n$$$.

For a given non-negative integer $$$m$$$ you can choose any binary string $$$P$$$ of length $$$n$$$ which contains $$$m$$$ $$$1's$$$ and $$$(n-m)$$$ $$$0's$$$.

Let the binary string $$$T = S \oplus P$$$, where $$$\oplus$$$ denotes Bitwise XOR

What are the maximum number of contiguous substrings of length $$$2$$$ in $$$T$$$ which are equal to $$$'11'$$$.

Solve the above problem for every $$$m(0 \le m \le n)$$$ .

$$$^\dagger$$$ A binary string is a string which only contains $$$0's$$$ and $$$1's$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

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

The second line of each testcase contains a binary string $$$S$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$

Output

For each test case, print $$$n+1$$$ space seperated integers — the required answer for every $$$m(0 \le m \le n)$$$.

Example
Input
4
3
010
3
011
4
0011
5
11100
Output
0 1 2 0 
1 2 1 0 
1 2 3 2 1 
2 3 4 3 2 1
Note

In the $$$1^{st}$$$ test case,

  1. For $$$m = 0$$$, let $$$P = 000$$$, then $$$T = 010 \oplus 000 = 010$$$, so total number of contiguous substrings of length $$$2$$$ in $$$T$$$ which are equal to $$$'11'$$$ are $$$0$$$.
  2. For $$$m = 1$$$, let $$$P = 001$$$, then $$$T = 010 \oplus 001 = 011$$$, so total number of contiguous substrings of length $$$2$$$ in $$$T$$$ which are equal to $$$'11'$$$ are $$$1$$$.
  3. For $$$m = 2$$$, let $$$P = 101$$$, then $$$T = 010 \oplus 101 = 111$$$, so total number of contiguous substrings of length $$$2$$$ in $$$T$$$ which are equal to $$$'11'$$$ are $$$2$$$.
  4. For $$$m = 3$$$, let $$$P = 111$$$, then $$$T = 010 \oplus 111 = 101$$$, so total number of contiguous substrings of length $$$2$$$ in $$$T$$$ which are equal to $$$'11'$$$ are $$$0$$$.