Busy Beaver は大統領選に出馬することを決意した。あいにく、唯一のライバルである Lazy Lemur が強敵すぎて、通常の手段では勝てそうにない。そこで彼は、すべての有能な政治家が行うように、ゲリマンダリングによって選挙を不正操作することにした！

選挙を不正操作せよ

Busy Beaver の国は、$1$ から $N$ まで番号が振られた $N$ 個の都市が一直線に並んでいる。各都市は Lazy Lemur か Busy Beaver のどちらかに投票し、Lazy Lemur への投票は $0$、Busy Beaver への投票は $1$ で表される。Busy Beaver は $N$ 個の都市を $K$ 個の空でない連続する都市のブロック（選挙区）に分割できる。$K$ が $1$ から $N$ までのすべての値について、Busy Beaver は彼への投票数が Lazy Lemur への投票数を厳密に上回る選挙区の数を最大化したいと考えている。

$K = 1, \dots, N$ のそれぞれについて、彼が勝てる選挙区の最大数を求めるのを手伝ってくれないか。

入力

各テストケースには複数のテストケースが含まれる。最初の行にはテストケースの数 $T$ ($1 \le T \le 10^4$) が含まれる。各テストケースの説明は以下の通りである。

各テストケースの最初の行には、都市の数を表す整数 $N$ ($1 \le N \le 10^5$) が含まれる。

各テストケースの2行目には、$0$ と $1$ からなる長さ $N$ の文字列 $s$ が含まれる。ここで $s_i$ が $0$ ならば $i$ 番目の都市の投票は Lazy Lemur が獲得し、$1$ ならば $i$ 番目の都市の投票は Busy Beaver が獲得したことを示す。

すべてのテストケースにおける $N$ の総和は $10^5$ を超えないことが保証されている。

出力

各テストケースについて、$N$ 個の整数を出力せよ。ここで $K$ 番目の整数は、$N$ 個の都市を $K$ 個の空でない連続するブロックに分割したときに、Busy Beaver への投票数が厳密に多い選挙区の最大数を表す。

スコアリング

• ($10$ 点) すべてのテストケースにおける $N$ の総和は $100$ 以下である。
• ($25$ 点) すべてのテストケースにおける $N$ の総和は $3000$ 以下である。
• ($65$ 点) すべてのテストケースにおける $N$ の総和は $10^5$ 以下である。

入出力例

入力 1

3
3
000
5
01101
8
11011011

出力 1

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

注記

テストケースは $3$ つある。

最初のテストケースでは、すべての都市が Lazy Lemur に投票しているため、Busy Beaver はどの選挙区でも勝つことができない。

2番目のテストケースでは、都市は $5$ つある。$K = 3$ のとき、都市を $[1, 3]$、$[4, 4]$、$[5, 5]$ という部分配列に分割することで、Busy Beaver は $2$ つの選挙区で勝つことができる。$[1, 3]$ では $3$ 都市中 $2$ 都市が彼に投票している。$[4, 4]$ では $1$ 都市のみで彼に投票していないため、彼はこの選挙区で負ける。$[5, 5]$ では $1$ 都市が彼に投票しているため、彼はこの選挙区で勝つ。Busy Beaver が $2$ つを超える選挙区で勝つことは不可能であることが証明できる。

$[1, 2]$、$[3, 4]$、$[5, 5]$ という部分配列に分割した場合は、$1$ つの選挙区でしか勝てないことに注意せよ。具体的には、$[1, 2]$ と $[3, 4]$ のそれぞれで $1$ 都市しか獲得できておらず、どちらの選挙区でも厳密な過半数を獲得できていない。