Busy Beaver has decided to run for president. Unfortunately, his only other rival, Lazy Lemur, is too strong, and Busy Beaver can't win using normal means. Therefore, he does what all good politicians do: rig the election via gerrymandering!

Busy Beaver's country consists of $N$ cities in a row numbered $1$ to $N$. Each city votes either Lazy Lemur or Busy Beaver as president, represented by a $0$ if the vote is for Lazy Lemur and a $1$ if the vote is for Busy Beaver. However, Busy Beaver gets to split the $N$ cities into $K$ nonempty blocks of contiguous cities, where each block is a district. For every value of $K$ from $1$ to $N$, Busy Beaver wishes to maximize the number of districts that have strictly more votes for him than Lazy Lemur.

Can you help Busy Beaver find the maximum number of districts with strictly more votes for $K = 1, \dots, N$?

Input

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

The first line of each test case contains one integer $N$ ($1 \le N \le 10^5$) describing the number of cities.

The second line of each test case contains a string $s$ of $0$'s and $1$'s of length $N$, where $s_i$ being $0$ denotes Lazy Lemur winning the $i^\text{th}$ city's vote and a $1$ denoting Busy Beaver winning the $i^\text{th}$ city's vote, for each $i$ from $1$ to $N$.

It is guaranteed that the sum of $N$ over all test cases does not exceed $10^5$.

Output

For each test case, output $N$ integers, where the $K^\text{th}$ integer represents the maximum number of districts with strictly more votes for Busy Beaver after splitting the cities into $K$ nonempty blocks of contiguous cities.

Scoring

• ($10$ points) The sum of $N$ across all test cases is at most $100$.
• ($25$ points) The sum of $N$ across all test cases is at most $3000$.
• ($65$ points) The sum of $N$ across all test cases is at most $10^5$.

Examples

Input 1

3
3
000
5
01101
8
11011011

Output 1

0 0 0
1 1 2 2 3
1 2 3 4 4 5 5 6

Note

There are $3$ test cases.

In the first test case, Busy Beaver can never win any districts because every city is voting for Lazy Lemur.

In the second test case, there are $5$ cities. For $K = 3$, Busy Beaver can win $2$ districts by splitting the cities into districts using the subarrays $[1, 3]$, $[4, 4]$, and $[5, 5]$. In $[1, 3]$, $2$ out of the $3$ cities vote for him. He loses the subarray $[4, 4]$ because the one city there does not vote for him. He wins the subarray $[5, 5]$ because the one city there votes for him. It can be proven that Busy Beaver cannot win more than $2$ districts.

Notice that splitting into subarrays $[1, 2]$, $[3, 4]$, and $[5, 5]$ would only win him $1$ district. In particular, he wins only one city in each of $[1, 2]$ and $[3, 4]$, and thus does not hold a strict majority in either district.