B. Simple Update - II
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$$$ and an integer $$$k$$$.

You are allowed to do the following operation on $$$s$$$ :

  1. Choose any $$$i(k \le i \le n-k)$$$;
  2. Update all $$$s_{i},s_{i-1},s_{i-2},...,s_{i-k+2},s_{i-k+1}$$$ to $$$1$$$;
  3. Update all $$$s_{i+1},s_{i+2},s_{i+3},...,s_{i+k-1},s_{i+k}$$$ to $$$0$$$.

For every $$$k(1 \le k \le ⌊\frac{n}{2}⌋)$$$, find the minimum number of above operations required to do on $$$s$$$ to get maximum number of $$$1$$$'s in $$$s$$$.

$$$^\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 1000$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — 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^5$$$.

Output

For each test case, print $$$⌊\frac{n}{2}⌋$$$ integers — minimum number of above operations required to do on $$$s$$$ to get maximum number of $$$1$$$'s in $$$s$$$.

Example
Input
5
2
10
3
100
4
0110
5
10100
7
1010010
Output
0 
1 
3 0 
3 1 
5 2 1